网站推广机构百度网站推广
目录
前言
1. 二分查找（基础版）
2. 寻找左右端点
循环判断条件
求中间点
总结
前言
说起二分查找，也是一种十分常见的算法，最常听说的就是：二分查找只能在数组有序的场景下使用；其实也未必，只要能找到规律，也依然可以使用；本文我将分享一些有关二分查找算法的做题经验；
1. 二分查找（基础版）
注意：二分查找算法也并非是只能在数组有序的场景下使用，只要数据具有 " 二段性 " 就可以使用；
基础版的二分查找，没有那么多弯弯绕绕，以及边界情况；下面是一个基础版本的示例：
while( left <= right)
{int mid = left + (right - left) / 2;if(nums[mid] > target) right = mid - 1;else if(nums[mid] < target) left = mid + 1;else return mid;
}在计算中间点时比较推荐示例中的写法：
int mid = left + (right - left) / 2;这种方式可以有效的防止数据溢出；
由此可以总结出基础版本的二分模板：
while( left <= right)
{int mid = left + (right - left) / 2;if(...) right = mid -1;else if(...) left = mid + 1;else return ...;
}2. 寻找左右端点
这种方式的二分算法有比较经典的题目：
力扣中的第34道题：
这种类型再使用基础版本的二分就没法很好的解决：
使用基础版本只能找到一组目标值中的某一个，比如：
nums = [5,7,8,8,8,9]; // target = 8基础版本只能保证找到数组中的8（目标值），但是要知道目标值开始位置和解释位置就不行了；还需要进行一些操作，但这样就容易让时间复杂度降到 O(N)，也就是所有值都是目标值的情况；因此基础版本在这道题中并不是最优解；这时就可以使用二分的进阶版：寻找区间左右端点；
怎么找左右端点？
还是使用这个示例：
nums = [5,7,8,8,8,9];寻找端点版本，主要分成两种情况（设中间点为x）：
以寻找左端点为例（以下的示例都是以求左端点）：
- x < target：left = mid + 1；在区间[left，right]中找；
- x >= target：right = mid；
将数组划分成两个区间；right为什么是等于mid就一目了然了；
当mid在如图的位置时，如果right = mid + 1；那么剩下的区间就不会有target；
较为难的点就是细节的处理，这里很容易出错，一旦出错就会成死循环；
细节：求中间点、循环条件
循环判断条件
判断条件是：
while(left < right){...
}不需要判断是否相等，如果判断了就会死循环；
- x < target：left = mid + 1；
- x >= target：right = mid；
比如：
如果right == left时还进入循环判断，此时走的是 x >= target；right还是会在原来的位置；这样就会造成死循环；
求中间点
求中间点有两种：
// 第一种
mid = left + (right - left) / 2;// 第二种
mid = left + (right - left + 1) / 2;他们的区别在于当数组元素为偶数的时候：
第一种：
第二种：
求左端点只能使用第一种，否则也会造成死循环：
如果是第二种情况：
假设区间只剩两个端点：
使用第二种方法计算出的mid是右边的端点；那么当满足 x < target：left = mid + 1；时循环退出；如果满足的是 x >= target：right = mid；就会出现死循环；
而第一种：
当满足 x < target：left = mid + 1；时 left走到right位置，循环结束；
当满足的是 x >= target：right = mid；right走到mid位置（也就是left位置），循环结束；
总结一下：
// 寻找左端点
while(left < right) {int mid = left + (right - left) / 2;if(left < target) left = mid + 1;else right = mid;
}// 寻找右端点
while(left < right) {int mid = left + (right - left + 1) / 2;if(right > target) right = mid - 1;else left = mid;
}可以得出模板：
// 寻找左端点
while(left < right) {int mid = left + (right - left) / 2;if(...) left = mid + 1;else right = mid;
}// 寻找右端点
while(left < right) {int mid = left + (right - left + 1) / 2;if(...) right = mid - 1;else left = mid;
}提醒：注意本文对二分进行了模板的总结，切记不要一味的记忆模板，要基于理解去使用；
以下是一些题目练习：
x的平方根
在排序数组中查找元素的第一个和最后一个位置
山脉数组的峰顶索引
总结
以上便是本文的全部内容，希望对你有所帮助，最后感谢阅读！