查找——二分查找

蔚落 2022-03-27 03:46 502阅读 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

代码实现

  1. int BinSearch(List L,int key)
  2. {
  3.     int low=0,mid=0,i=-1,high=L.length-1;
  4.     while(low<=high)
  5.     {
  6.         mid=(low+high)/2;
  7.         if(L.r[mid]==key)//找到目标元素
  8.         {
  9.             i=mid;
  10.             break;
  11.         }
  12.         else if(L.r[mid]<key)low=mid+1;//从后半段查找
  13.         else high=mid-1;//从前半段查找
  14.     }
  15.     return i;//若返回-1代表查找失败
  16. }

性能分析

对于长度为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)

比较：

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

发表评论

表情：
评论列表 （有 0 条评论，502人围观）

还没有评论，来说两句吧...

相关阅读

    相关 二分查找(折半查找)

    二分查找 了解B+树的时候，看到了二分查找，发现自己只知道名称的意思是折半查找，却不知道是怎么去实现的。 后来查阅网上资料，发现二分查找必须要求数据是有序的，这样就

    川长思鸟来川长思鸟来/ 0 赞/ 407 阅读

    相关 查找——二分查找

    基本思想 二分查找是建立在有序顺序表基础上的！步骤如下： 1.      将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.    

    蔚落蔚落/ 0 赞/ 502 阅读