查找——二分查找

蔚落 2022-03-27 03:46 356阅读 0赞

## 基本思想 ##

二分查找是建立在有序顺序表基础上的！步骤如下：

1.      将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。

2.      若两者不相等，利用中间位置将表分成前后两个子表，如果中间位置记录的关键字大于给定K值则进一步查找前一子表，否则查找后一子表。

3.      重复以上两个步骤，直到找到满足条件的记录则查找成功，或者分解出的子表不存在，此时查找失败。

## 实例分析 ##

用二分查找法在有序表（6,12,15,18,22,25,28,35,46,58,60）查找12.

在查找中分别用low、high和mid记录表中的第一个、最后一个以及中间记录的位置。其中mid=(low+high)/2，当high<low时，查找失败。

分析过程图如下：

![1362322110_4284.JPG][]

## 代码实现 ##

int BinSearch(List L,int key)
    {
        int low=0,mid=0,i=-1,high=L.length-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(L.r[mid]==key)//找到目标元素
            {
                i=mid;
                break;
            }
            else if(L.r[mid]<key)low=mid+1;//从后半段查找
            else high=mid-1;//从前半段查找
        }
        return i;//若返回-1代表查找失败
    }

## 性能分析 ##

对于长度为n的有序表，只有一个元素仅需比较一次就可以得到查找结果，有两个元素需要比较两次，有4个元素需要比较3次，有8个元素需要比较四次……有2h-1个元素需要比较h次得到查找结果。

令：

n=1+2+4+8+……+2h-1=2h\-1

则在长度为n的有序表中最大查找长度为h，准确的说，当2h-1\-1＜n≤2h\-1时的最大查找长度为h，则

h=\[log2(n+1)\]

假设每个记录的查找概率相等，则二分查找成功的平均查找长度为

当n较大时，n+1/n近似为1，则有如下近似结果：

所以二分查找的平均查找长度数量级（算法时间复杂度）为O(log2n)

## 比较： ##

和上一篇： [查找——简单顺序查找][Link 1]相比，明显二分查找的性能较好，但由于简单顺序查找比较简单，再加之二分查找需要在有序表前提上进行，故在平时编程中使用较多。因此，对于有序表，多用二分查找较好~

[1362322110_4284.JPG]: https://img-my.csdn.net/uploads/201303/03/1362322110_4284.JPG
[Link 1]: http://blog.csdn.net/celte/article/details/8631905