【二分查找】
【思想】
用给定值与处在表的中间位置的数据元素的键值进行比较，确定给定值的所在区间，然后逐步缩小查找区间。重复以上过程知道找到或确认找不到该数据元素为止。
【ASL】
ASLb=
∑PiCi
=
(n+1)log2(n+1)/n -1
≈
log2(n+1) -1
【时间复杂度】
时间复杂度为O(log
2
n)
【优缺点】
（1）优点：时间性能相对于顺序查找要好,效率较高
（2）缺点：局限性大，只适用于顺序存储结构，即要求存储结构是顺序表或者顺序表中元素按键值的次序排列
【算法描述】
int SearchBin(SqTalbe T,KeyType key) /*在有序表T中，用二分查找法查找键值等于key的元素，变量low，high分别标记查找区间的下界和上界*/ { int low,high; low=1;high=T.n; //设置查找区间的初始值 while(low<=high) //当区间长度不为0时进行查找 { mid=(low+high)/2; //对区间进行折半 if(key==T.elem[mid],key) return mid; else if(key<T.clem[mid].key) high=mid-1; //若给定值小于区间的中值mid，则在前半区间查找 else low=mid+1; //若给定值大于区间的中值mid，则在后半区间查找 } return 0; //查找不成功，则返回0 }
