【数据结构】静态查找之二分查找

发布时间：2020-12-15 06:00:06 所属栏目：安全来源：网络整理

导读：【二分查找】查找（Binary Search），也叫折半查找，是一种静态表查找方法。【思想】用给定值与处在表的中间位置的数据元素的键值进行比较，确定给定值的所在区间，然后逐步缩小查找区间。重复以上过程知道找到或确认找不到该数据元素为止。【ASL】 ASL

【二分查找】

查找（Binary Search），也叫折半查找，是一种静态表查找方法。

【思想】

用给定值与处在表的中间位置的数据元素的键值进行比较，确定给定值的所在区间，然后逐步缩小查找区间。重复以上过程知道找到或确认找不到该数据元素为止。

【ASL】

ASL_b= ∑P_iC_i = (n+1)log₂(n+1)/n -1 ≈ log₂(n+1) -1

【时间复杂度】

时间复杂度为O(log ₂ 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
}