二分查找

     二分查找又叫折半查找 , 指的是每次查找的范围减半, 与枚举算法相比 ,二分查找具有比较次数少,查找速度快 , 平均性能好等优点,缺点是要求待查找的数据已被整理为有序列表 .

     二分查找的目标是对于有序列表 , 在其中查找指定的目标元素的位置 , 其基本思想是 : 在有序数列中 , 将列表中得中间位置元素与目标元素作比较 , 如果两者相等 ,则查找成功 ,否则将列表从中间位置分离开 , 分成前,后两个子列表 如果中间位置的元素大于目标元素,则进一步查找前一子列表, 否则进一步查找后一子列表 , 当然前提是 , 列表是从小到大排序的 ,重复以上步骤 ,直到查找到满足元素,

比如  有序列表 L = [ 1,4,8,9,12,63,79 ]

查找8

第一步 : 比较L中间的 9 和 目标元素 8 ,  9>8 ,再查找 [ 1,4,8 ]

第二部 : 比较 L 中间的 4 和 目标元素 8 , 4<8  ,再查找  [8 ]

第三部 : 找到 

#include <iostream>
#include <cstdio>
using namespace std ;
int Binary_Search(int L[], int key , int left ,int right )
{
  int mid ;
  while ( right >=left )
  {
     mid = left + (right -left)/2 ;
     if(L[mid] == key)
     {
      return mid ;
     }
     else if (L[mid] <key)
     {
      left = mid + 1 ;
      
     }
     else
     {
      right = mid - 1 ;
     }
  }
  
}
int main()
{
  int a[10] = {1, 4,8,9,12,63,79};
  cout<<Binary_Search(a,79,0,8);

  return 0 ;
}

可见二分查找算法的基本思想十分直观 , 易于理解 ,而且二分查找充分利用了元素的次序关系 ,采用分治策略,可在最坏的情况下用O(logN)完成查找任务 .

需要注意

(1) 数据范围.

         整形的范围是 -2^31 ~ 2^31-1 , 二分查找在求中间位置时 ,如果使用 int mid = (left + right ) /2 的形式 ,则 对于较大的 left 和 right ,有可能相加后超过整形的表示范围 , 得到错误的计算结果 , 因此应使用 int mid = left + (right - left ) /2 的形式 

(2) 边界确定

        边界确定涉及到二分查找的判断和赋值 ,如 right >left 还是 right >= left  ,right = mid -1  还是 right =mid ,甚至包括 right 的初始值是n 还是  n-1 .  边界必须要遵循一定的区间规则, 序列及其子序列的mid 和 right 都要表示统一的开闭区间 , 也就是说当 right = n 的时候 ,是左闭右开 的区间 [left, right) ,那么在取子序列的时候 , 仍然要保持左闭右开 .