【手绘漫画】面试必考之二分查找中回（修订版），（LeetCode 704题）
【手绘漫画】面试必考之二分查找中回（修订版），（LeetCode 704题）
我是管小亮
发布于 2020-04-20 16:00:56
发布于 2020-04-20 16:00:56
1、前言
上次讲到的更的二分查找模板在很多地方让我使用起来不是特别的舒服，感谢B站上的y大佬，让我找到了一个新的模板！！！
下面一起来看看吧！！！
本次的模板应对重复元素也可以~
2、代码
模板一：
// Cint lower_bound(int* nums, int numsSize, int target){ int left = 0; int right = numsSize-1; while(left < right){ // 搜索区间[first, last)不为空 // 防溢出 int mid = left + right >> 1; if(nums[mid] >= target) right = mid; else left = mid + 1; } return left; // right也行，因为[left, right)为空的时候它们重合}首先一定要明确，数组是升序的！！！
如果中点大于等于 target，表示目标在左侧，数组范围应该从 [left, right] 变成 [left, mid]，否则，就从 [left, right] 变成 [mid+1, right]。
为什么 right 不加一？
因为是大于等于，带着等于，也就是 mid 有可能是我们的解！！！
模板二：
// Cint lower_bound(int* nums, int numsSize, int target){ int left = 0; int right = numsSize-1; while(left < right){ // 搜索区间[first, last)不为空 // 防溢出 int mid = left + right + 1 >> 1; // 防止死循环，mid加1 if(nums[mid] <= target) left = mid; else right = mid + 1; } return left; // right也行，因为[left, right)为空的时候它们重合}首先一定要明确，数组是升序的！！！
如果中点小于等于 target，表示目标在右侧，数组范围应该从 [left, right] 变成 [mid, right]，否则，就从 [left, right] 变成 [left, mid+1]。
为什么 left 不加一？
因为是小于等于，带着等于，也就是 mid 有可能是我们的解！！！
- 模板一：区间
[left, right]划分成[left, mid]和[mid + 1, right]时，其更新操作是right = mid或者left = mid + 1;，计算mid时不需要加1。 - 模板二：区间
[left, right]划分成[left, mid - 1]和[mid, right]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
3、实例（LeetCode 704题）
首先看一下题目，
代码：
int search(int* nums, int numsSize, int target){ int left=0; int right=numsSize-1; while(left<right){ int mid=left+right >> 1; if(nums[mid]>=target){ right=mid; } else{ left=mid+1; } } if(nums[left]==target) return left; return -1;}
作为最经典的二分查找题，这个题依旧复合我们的模板，没错就是 模板一！！！
唯一不同的是，要注意判断结果，不能只写个 left ，因为是存在 -1 的情况的，加个 if(nums[left]==target) return left; 就好了。
这里自然又更容易的方法，但是 练习模板，万法接通，每日一遍，养成习惯！！！
附上最经典的二分查找解法：
// Cint search(int* nums, int numsSize, int target){ int left = 0; int right = numsSize - 1;
while (left <= right) { // 最好这么写，不然会内存溢出 // 同时还能减少运行时间！！！ int mid = (left + right) >> 1; // 等于的情况最简单，首先判断，没准一下就中了！ if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { // 左边界更新为 mid + 1 left = mid + 1; } else { // 右边界更新为 mid - 1 right = mid - 1; } } return -1;}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读