二分查找
二分查找
简介
二分查找作为高效的查找算法，可以说是每个学计算机的都应该懂的，在每年的面试中，可以说是必须考察的点；
其实我们小时候就用过这个算法，只是没注意罢了，比如一本书300页，你要找第100页，你翻到了第20页，那么你肯定向后翻，你又翻到了第80页，你肯定继续向后找，每次砍掉一些。还比如英语字典，是按照单词的字典序排列的，你也是利用上面的算法在找。其实这就是二分查找。
适用范围
有序的线性表（一定得是数组存储的，由于需要快速取得对应位置的值）
需要注意的问题
int binarySearch(int arr[], int beg, int end, int target)
1、安全性检测
- beg 与 end 必须>=0
- beg <= end
-
end <= 数组的大小
对应的检测语句如下：assert(beg >= 0 && beg <= end && end < sizeof(arr)/sizeof(int)); /*sizeof这个语法貌似不一定对*/
2、特殊判断
如何出入的是一个空数组，此时beg==end==0,计算mid会得0，然后访问arr[0]会报错所以应该加一句：
if (beg == end && beg == 0)
return -1;
3、注意mid的求法：
/*method1:*/ int mid = (beg + end) / 2; /*method2:*/ int mid = beg + (end - beg) /2 ; /*method3:*/ int mid = beg + ((end - beg) >> 1);
方法1：存在溢出的风险例如0x02 0x7fffffff
方法2、方法3：对于现代的编译器，两者执行效率应该一样；
注意：加法的优先级大于右移，所以需要在>>操作加括号(掉过坑，冏)
在何的博文中有一个网友提到的(beg + end)/2的语意是向0取整而不是向下取整，比如（-3 + 2）/ 2 == 0的，而beg + (end - beg) / 2是向下取整则为-1
4、循环的结束条件
循环和递归程序应注意的三点：1、初始条件；2、转换条件；3、终止条件；
对于二分需要注意的是终止条件情况比较复杂，可以利用画图来描述
beg----------mid------------end
beg <= mid <= end 是天然成立的 分类讨论： arr[mid] < target 说明目标值在mid的右边
arr[mid] == target 恰好等于目标值
arr[mid] > target 目标值在mid的左边
最终结束条件（除随机选择一个与目标值相等的需求）是beg == end 或者beg + 1 == end刚好在临界点，判断条件一般是while (beg + 1 < end)可以避免死循环
分类(参考编程之美)
给定一个有序(不降序)数组arr，求解任意一个i使得arr[i]等于v，不存在则返回-1
/*给定一个有序(不降序)数组arr，求解任意一个i使得arr[i]等于v，不存在则返回-1*/
int findEqual(int arr[], int beg, int end, int target)
{
assert(0 <= beg && beg <= end);
int mid = -1;
int ret = -1;
while (beg <= end)
{
mid = beg + ((end - beg)>>1);
if (arr[mid] == target)
{
ret = mid;
break;
}else if (arr[mid] > target){
end = mid - 1;
}else {
beg = mid + 1;
}
}
return ret;
}
给定一个有序(不降序)数组arr，求解最小的i使得arr[i]等于v，不存在则返回-1
/*给定一个有序(不降序)数组arr，求解最小的i使得arr[i]等于v，不存在则返回-1*/
int findMinEqual(int arr[], int beg, int end, int target)
{
assert(0 <= beg && beg <= end);
int mid = -1;
int ret = -1;
while (beg <= end)
{
mid = beg + ((end - beg)>>1);
if (arr[mid] == target)
{
if (mid - 1 >= 0 && arr[mid - 1] == target)
end = mid - 1;
else{
ret = mid;
break;
}
}else if (arr[mid] > target){
end = mid - 1;
}else {
beg = mid + 1;
}
}
return ret;
}
给定一个有序(不降序)数组arr，求解最大i使得arr[i]等于v，不存在则返回-1
/*给定一个有序(不降序)数组arr，求解最大i使得arr[i]等于v，不存在则返回-1*/
int findMaxEqual(int arr[], int beg, int end, int target)
{
assert(0 <= beg && beg <= end);
int mid = -1;
int ret = -1;
while (beg <= end)
{
mid = beg + ((end - beg)>>1);
if (arr[mid] == target)
{
if (mid + 1 <= end && arr[mid + 1] == target)
{
beg = mid + 1;
}else{
ret = mid;
break;
}
}else if (arr[mid] > target){
end = mid - 1;
}else {
beg = mid + 1;
}
}
return ret;
}
给定一个有序(不降序)数组arr，求解最大i使得arr[i]小于v，不存在则返回-1
/*给定一个有序(不降序)数组arr，求解最大i使得arr[i]小于v，不存在则返回-1*/
int findMaxLess(int arr[], int beg, int end, int target)
{
assert(0 <= beg && beg <= end);
int mid = -1;
while (beg + 1 < end)
{
mid = beg + ((end - beg)>>1);
if (arr[mid] >= target)
{
end = mid - 1;
}else{
beg = mid;
}
}
if (arr[end] < target)
return end;
else if (arr[beg] < target)
return beg;
else
return -1;
}
给定一个有序(不降序)数组arr，求解最小i使得arr[i]大于v，不存在则返回-1
/*给定一个有序(不降序)数组arr，求解最小i使得arr[i]大于v，不存在则返回-1*/
int findMinGreat(int arr[], int beg, int end, int target)
{
assert(0 <= beg && beg <= end);
int mid = -1;
while (beg + 1 < end)
{
mid = beg + ((end - beg)>>1);
if (arr[mid] <= target)
beg = mid + 1;
else
end = mid;
}
if (arr[beg] > target)
return beg;
else if (arr[end] > target)
return end;
else
return -1;
}
/*别人的写法*/
int findOther(int arr[], int beg, int end, int target)
{
int mid = -1;
while (beg <= end)
{
mid = beg + (end - beg) / 2;
if (arr[mid] <= target)
beg = mid + 1;
else
end = mid - 1;
}
if (arr[beg] <= target)
return -1;
else
return beg;
}
一些不常见的写法
引用貌似得翻墙
声明
由于水平有限，若发现错误请告知，共同进步；
参考
1、二分查找(Binary Search)需要注意的问题，以及在数据库内核中的实现
2、编程之美p261页
下期预告
字符串专题，欢迎继续支持
