二分查找又叫折半查找 , 指的是每次查找的范围减半, 与枚举算法相比 ,二分查找具有比较次数少,查找速度快 , 平均性能好等优点,缺点是要求待查找的数据已被整理为有序列表 .
二分查找的目标是对于有序列表 , 在其中查找指定的目标元素的位置 , 其基本思想是 : 在有序数列中 , 将列表中得中间位置元素与目标元素作比较 , 如果两者相等 ,则查找成功 ,否则将列表从中间位置分离开 , 分成前,后两个子列表 如果中间位置的元素大于目标元素,则进一步查找前一子列表, 否则进一步查找后一子列表 , 当然前提是 , 列表是从小到大排序的 ,重复以上步骤 ,直到查找到满足元素,
比如 有序列表 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) ,那么在取子序列的时候 , 仍然要保持左闭右开 .
标签:二分,right,int,mid,查找,left From: https://blog.51cto.com/u_15970235/6064119