共计 5616 个字符，预计需要花费 15 分钟才能阅读完成。
导语：二分查找是对一个有序数组的搜索算法，因为每次都是折半搜寻，所以工夫复杂度未O(LogN)，然而在编写二分查找时外面蕴含了一些细节，上面将给大家讲述一下如何利用二分查找找到目标值、第一个比目标值大的值和最初一个比目标值小的值。
一、判断是否蕴含目标值（简略二分查找）
比方当初给你一个有序的数组nums，问你数组内是否蕴含目标值target，这个能够套用最根底的模板
public boolean binary_search(int[] arr) {
int left = 0, right = arr.length - 1; // 细节 1
while (left <= right) { // 细节 2
int mid = (right - left) >> 2 + left;
if (arr[mid] == target) {return true} else if (arr[i] > target) {right = mid - 1; // 细节 3} else if (arr[i] < target) {left = mid + 1; // 细节 3}
}
return false; // 细节 4
}挡你刷的二分查找题目比拟多，看的题解比拟多的时候可能会有上面的疑难
- 到底是
right的初始值是arr.length还是arr.length - 1？ while的条件到底是<还是<=？right和left什么时候须要加 1 减 1？- 如果要返回坐标，应该返回啥
前面两个问题其实是第一个问题引出的，咱们先解决第一个问题
-
right是arr.length - 1还是arr.length，下面的例子是arr.length - 1，取arr.length - 1能够认为是在对区间[left, right]进行搜寻（两边闭合），如果让right等于arr.length，那么right曾经越界了，所以能够认为他是在对[(left, right)进行搜寻（左闭右开）留神
right的取值会影响框架的其余地位 -
while中<和<=次要体现在终止条件的不同，如果是<，他的终止条件是left == right，如果是<=，则是left + 1 == right，不难发现<不会解决left == right的状况，如果你应用了<，须要多思考left==right的状况如数组{1, 2, 3, 4, 5}, target = 5, 如果 while 修的是 <，返回的是 false如果硬是要用
<=，其实咱们曾经晓得他漏了判断left==right的状况了，咱们只有在最初补上就行return arr[left] == target; -
最初就是
left和right加 1 减 1 的时了，需不需要加一减一取决于你的right是怎么定义的- 如果是两边闭合的，当你检测完
mid不是你想要的，下一步应该查看[left, mid - 1]和[mid + 1, righjt]呀， - 如果是做闭右开，当你查看完
mid不是你想要的值，下一步应该查看[left, mid)和[mid + 1, right)呀，所以right不必加 1
- 如果是两边闭合的，当你检测完
所以二分查找怎么写是由
right的取值决定的
二、找到目标值坐标否则返回 -1
有了下面等到根底，咱们能够很快的写出代码
-
right = arr.length - 1代码如下：
public int binarySearch(int[] nums, int target) { int left = 0; right = nums.length - 1; while (left <= right) {int mid = (left + (right - left) >> 1); if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid + 1;} return -1 } } -
right = nums.length代码如下
public int binarySearch(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) {int mid = (left + (right - left) >> 1); if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid;} } return -1; }
这里还是比拟容易了解的
三、找到第一次呈现指标元素的下标
例如给定一个数组 [11, 22, 33, 44, 44, 44, 55]，若target 等于 44，二分查找的后果应该为 3，这个时候咱们能够先用下面第二点的代码找到 44，而后往左边始终找，咱们也能够再二分查找模板上进行大量批改实现该性能
同样分成两种状况：
-
right = arr.length - 1这时是对两边闭合的区间进行搜寻，咱们只须要改一下原来的模板就行了
public int leftBound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right){int mid = left + ((right - left) >> 1); if (nums[mid] == target) {right = mid - 1;} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;} } return left; }为什么最初返回的是
left呢，大家能够剖析一下：如果target存在于数组中，最初一次循环时left和right都指向target，循环完结后right通过mid(left) - 1，所以left才是目标值，如果目标值不在数组里，最初一次循环left和right都会指向第一个比目标值大的数，right被减去 1 后不再循环，最终返回的left能够了解为 数组中比目标值的数的个数，也能够认为是寻找大于等于目标值的数的索引，则个语义很重要如果题目要求找不到返回 -1，那么就须要加上一些判断。依据下面的剖析，
left的取值范畴应该是[0, len]，因而咱们须要判断left等于len（当target大于这个数组所有的数，最初left = mid + 1所导致），或者left = 0然而target != nums[0]（当target小于所有数，最初left = 0所导致），又或者目标值在数组范畴里却不在数组中，那就是target != nums[left]，所以咱们徐娅加上两个非凡判断残缺代码如下：
public int left_bound(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) {int mid = ((right - left) >> 1) + left; if (arr[mid] == target) {right = mid - 1;} else if (arr[mid] > target) {right = mid - 1;} else {left = mid + 1;} } if (left >= arr.length || arr[left] != target) {return -1;} return left; } -
right = arr.length如果对返回值没有作要求，代码如下：
public int leftBound(int[] nums, int target) { int left = 0, right =nums.length; while (left < right) {int mid = left + ((right - left) >> 1); if (nums[mid] == target) {right = mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid;} } return left; }最初为什么返回
left呢？如果目标值在数组中，最终left = right且会指向第一个target，如果目标值不在数组中，最初一次循环时left和right会指向第一个比目标值大的数，这其实和下面的状况雷同，最终返回的left能够了解为 数组中比目标值的数的个数如果要返回 - 1 呢？咱们也要思考
keft的取值范畴，应该是[0, len]，所以当目标值比数组元素大时，left = right = len，当目标值比所有制小的时候left = right = 0，所以这次的判断和下面的一样public int left_bound(int[] arr, int target) { int left = 0, right = arr.length; while (left < right) {int mid = ((right - left) >> 1) + left; if (arr[mid] == target) {right = mid;} else if (arr[mid] > target) {right = mid;} else {left = mid + 1;} } if (left == arr.length) {return -1;} return arr[left] == target ? left : -1; }
大家要思考当目标值比数组所有值都大的状况 left 和right指向哪里，最初应该是走 mid = left，走arr[mid] < target 的分支，letf = mid + 1，left等于 right 等于arr.length
四、找到最初一次呈现指标元素的下标
同样的，咱们来找一下最初一个指标元素
-
right = arr.length - 1代码如下
public int rightBound(int[] nums, int target) { int left = 0, right =nums.length - 1; while (left <= right) {int mid = left + ((right - left) >> 1); if (nums[mid] == target) {left = mid + 1;} else if (nums[mid] < target) {left = mid + 1 ;} else {right = mid - 1;} } return left - 1 or right; }大家剖析一下，最初咱们应该返回的是什么，应该是
left - 1，如果目标值在数组里，最初一次遍历left = right = 最初一个数字，而后left被 +1，所以是left - 1 or right。如果目标值不在这个数组中，最初一次迭代left = right= 第一个比目标值大的数的索引，最初饭返回的是left - 1，能够了解成 比目标值小的最初一个元素的索引如果要返回 – 1，咱们能够看看
right的取值范畴应该是[-1, len - 1]，如果目标值太小，right应该是 -1，如果太大，right应该是len，所以残缺代码为private int right_bound(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) {int mid = ((right - left) >> 1) + left; if (arr[mid] == target) {left = mid + 1;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;} } // left = right + 1, right 指向的如果越界了 if (right < 0 || arr[right] != target) {return -1;} return right; } -
right = arr.length如果是这种状况，代码应该是
public int rightBound(int[] nums, int target) { int left = 0, right =nums.length; while (left < right) {int mid = left + ((right - left) >> 1); if (nums[mid] == target) {left = mid + 1;} else if (nums[mid] < target) {left = mid + 1 ;} else {right = mid;} } return left - 1 or right - 1; }为什么是
left - 1呢，设想一下当初mid指向目标值，当初left = mid, right = mid + 1，mid 趋势是目标值，最初left = mid + 1，所以目标值在left - 1。如果目标值不在数组中，left = right = 第一个比目标值大的数，所以返回的是 最初一个比目标值小的数的索引如果你心愿返回 -1，
left的取值范畴是[0, len]，如果目标值太大，这时候 left 应该是len·，如果太小，left = right = 0，综上，代码如下
private int right_bound(int[] arr, int target) {
int left = 0, right = arr.length;
while (left < right) {int mid = ((right - left) >> 1) + left;
if (arr[mid] == target) {left = mid + 1;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid;}
}
if (left == 0) {return -1;}
return arr[left - 1] == target ? left - 1 : - 1;
}五、理论利用
形如：
for i in range(num1):
for j in range(num2)这种工夫复杂度为 O (N2) 的找最目标值问题，都能够用二分查找解决，其中寻找左边界的二分查找用的最多，上面是 LeetCode 中常见的题目：
- LeetCode 875 爱吃香蕉的 CoCo，
- LeetCode 1011 在 D 天送达包裹的能力
- LeetCode 410 宰割数组最大值
当然啦，二分查找能够和其余算法联合，例如高楼丢鸡蛋问题也是能够应用二分查找优化的，写完本文，我对本人的要求是把握剖析边界的办法以及学会寻找大于等于目标值的二分查找
参考
本文大量参考博主 labuladong 的文章，平时仓看他的文章，写得很好，大家有趣味能够去看看
- 我作了首诗，保你闭着眼睛也能写对二分查找，labuladong https://mp.weixin.qq.com/s/M1…