算法：二分查找解题之核心思路(新颖)
原创
算法：二分查找解题之核心思路(新颖)
原创
二分查找的概述：
二分查找，也叫折半查找，一个比较简单的算法，能在有序数组中，以O(logn)的时间复杂度，快速找出符合要求的答案。在n非常庞大的情况下，相比于遍历数组，二分查找的效率是非常高的。 虽然二分查找的思路理解起来非常简单，但是真正到了做题的时候，如果不能彻底参透该算法，做到具体问题具体分析，可能就会漏洞百出了。正如网上资料所说：
“二分查找很好写，却很难写对，据统计只有10%的程序员可以写出没有bug的的二分查找代码。出错原因主要集中在判定条件和边界值的选择上，很容易就会导致越界或者死循环的情况。”
今天，我就来分享一下我做二分查找的核心思路和心得体会。
核心思路：
如果仅仅只是口头阐述，而不结合具体例子，想必大家是很难理解的，这里我找出了几个二分查找题型的不同种边界情况。带大家分析一下对应的做题思路。
常见的二分查找题解模样（伪代码）
int l = 0; //l <= 答案范围的最小值
int r = n; //r >= 答案范围的最大值
while(l < r){ //while循环条件 l < r 是可以做出任何题目的,所以不用做什么改变
long long mid = (l + r) >> 1; //mid有时应为 (l + r + 1) >> 1, 受下面l和r的取值影响
if(a[mid] < target){ //这里的边界条件要根据具体题目而变, 且会影响下面l和r的取值
l = mid + 1; //应结合具体请情况
}else{
r = mid; //应结合具体情况
}
}
return l; //while循环条件为 l < r时,最终答案永远为l上面只是列出了二分查找题解的基本架构, 并不是针对哪道题的模板
浏览我的注释,大家会发现,不同的二分查找题型,只是while循环里面的那块在微调,while循环外面的代码几乎一致
下面我来简单分析几种题型,希望大家能理解我的核心思路,做到一通百通.
注意: 我对二分查找题型分类的情况可能会和其他大佬不同,我是按照中值mid的取值对二分查找题型进行分类的,
因为mid取值只有两种情况: mid = (l + r) >> 1 或 mid = (l + r + 1) >> 1
若按照不同题目情境下, 不同的边界判断条件来讲解，小白会容易混乱。
而其实，在一个题目情境下，边界条件可以为nums[mid] < target，也可以为nums[mid] <= target等等，只是不同的边界条件，l和r的取值会不同而已。
所以根据边界条件来分情况会比较繁杂混乱，但按照mid的取值来分情况，那么只有两种情况。
1、中值 mid = (l + r + 1) >> 1的情况
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
//答案在数组元素下标为[l,r]的区间内
while(l < r){
long long mid = (l + r + 1) >> 1; //因为l=mid,所以在折半取值时,mid应优先取ceil((l+r)/2),避免死循环
if(nums[mid] <= target){
l = mid; //nums[mid]可能为答案
}else{
r = mid - 1;//nums[mid]肯定不是答案了,就将该mid踢出答案所在的[l,r]区间内
}
}
if(nums[l] == target) return l;
return -1;
}
};
1、这题target可能不存在, 数组在l和r之间的所有元素都可能为答案.
2、判断时，当元素 <= target时，可能为答案，若元素 >target, 那么一定不可能是答案.
因此，当nums[mid] <= target 时, mid指向的值可能为答案,因此l=mid, 若l=mid+1,则该元素就不在答案可能在的[l,r]区间了
else 当nums[mid] > target 时, mid指向的值肯定不可能是答案,所有r = mid - 1,将该元素踢出[l,r]区间
3、分析到这里,l和r的分条件取值已经写好了, 只有mid的表达式还没确定.
为什么是(l + r + 1) >> 1, 而不是(l + r) >> 1呢?
根据上面l和r的取值可以判断.
当l+1=r的情况下,
l所指的元素可能为答案,所以l在判断后会一直=mid,
若mid = (l + r) >> 1, 那么mid会一直=l
那么就陷入死循环了
而mid = (l + r + 1) >> 1, 那么mid计算后就会等于r,此时就能正常得出答案.来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-search
2、中值 mid = (l + r) >> 1的情况
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int n = letters.size();
int l = 0;
int r = n;
//答案在数组元素下标为[l,r]的区间内
while(l < r){
long long mid = (l + r) >> 1;
if(letters[mid] <= target){ //答案必须>target, 若letters[mid]<=target,则一定不可能是答案了
l = mid + 1; //letters[mid]肯定不可能是答案了，就将该mid踢出答案所在的[l,r]区间内
}else{
r = mid; //letters[mid]可能为答案
}
}
return letters[l % n];
}
};
1、这题，当元素 > target时, 可能为答案, 若元素 <= target, 那么一定不可能是答案
2、当letters[mid] <= target 时, mid指向的值肯定不可能是答案,所以l = mid + 1,将该元素踢出[l,r]区间
else 当letters[mid] > target 时, mid指向的值可能为答案,因此r=mid, 若r=mid-1,则该元素就不在答案可能在的[l,r]区间了
3、分析到这里,l和r的分条件取值已经写好了, 只有mid的表达式还没确定.
为什么是(l + r) >> 1, 而不是(l + r + 1) >> 1呢?
根据上面l和r的取值可以判断.
当l+1=r的情况下,
r所指的元素可能为答案,所以r在判断后会一直=mid,
若mid = (l + r + 1) >> 1, 那么mid会一直=r
那么就陷入死循环了
而mid = (l + r) >> 1, 那么mid计算后就会等于l,此时就能正常得出答案.来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target
总结：
认真理解后，是不是觉得按照mid取值对二分查找进行分类，相比于按照边界条件来分类会清晰许多呢？其实在做题时，
while（l < r）{}以外的所有代码都是类似的, 根据题目情况稍微变一下就好了,如 l 和 r 的初始值为多少.
在写while循环里面的代码时, 完全可以先让mid = (l + r) >> 1, 然后往下写,当你选取了边界条件后, 并根据边界条件写出了 l 和 r 的取值等式后, 再分析特殊情况, 当l + 1 =r 时, 按照你写的l 和 r的取值等式, 是否会造成死循环, 如果会, 再将mid改为(l + r + 1) >> 1即可.
而 对于 l 的取值 l = mid+1 还是 l = mid, 对于 r 的取值 r = mid - 1还是 r = mid，都要根据你选取的边界条件来判断，不同边界条件，l和r的取值不同，但是思路都是一样的，若mid指向的元素可能为答案时，就不能将mid踢出答案所在的[l,r]区间，具体结合我上面的两个例子。
完结撒花~新人出道不易，希望大家可以喜欢+收藏哦！
如果上述分享有不妥之处，欢迎大家在评论区斧正！
之后我还会陆续更新算法心得和前后端技术的文章，欢迎大家关注支持~
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
