介绍
简介
条件：数组有序
作用：查找数组中的某个值
算法描述： 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
基本模版
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2; //1
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
其中的'...'是一些细节的地方，可以根据之后题目的要求，进行求解。
其中需要注意的是，标记为1的地方，也就是求解mid值的代码，当然也可以写成int mid = (left + right) / 2;但是为了防止left + right的值过大导致的内存溢出，一般将其写为int mid = left + (right - left) / 2的形式。
基本的二分搜索
二分查找我们能想到的就是用来搜索一个值，如果存在，返回其索引，否则返回 -1。
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) { //注意
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
下面简单介绍其中涉及到的一些细节问题：
- while中为什么是
<=而不是<？
总结来说，就是考虑区间[left ,right]还是区间[left, right),详细说明如下。
注意到其中的right取值为nums.length - 1,那么为了能够将数组中的值全部访问到，right必然需要能够被访问到，即当前的搜索区间在[left, right]之间。
那么停止搜索有两种情况，一种是找到了target值，直接返回mid，还有一种就是不满足while循环条件了，也可以理解为当前的搜索区间不存在了。考虑当left == right的时候，此时区间可以写成为[left, left]，区间里面还是有值的，能够进入while循环，之后就有三种情况了，一种直接返回，一种是left = left + 1, 还有一种是right = right - 1（因为之前是left == right == mid），不过不论是哪一种，都存在left + 1 == right，也就是说最终的终止状态应该是left + 1 == right。或者可以简单的通过while(left <= right)分析出终止条件。
为了更明显的进行对比，可以考虑while(left < right)的终止条件，也就是当left == right的时候，就停止。考虑left == right的情况，此时区间为[left, left]，但是此时的是无法进入循环的，所以区间形式写成[left, left)更为合适。所以此时，是少考虑一种情况的，那么此时可以尝试right = nums.length会正常运行。
更多细节方面内容可以参考博客
二分查找细节详解
二分查找的坑点与总结
实例
01-寻找旋转排序数组中的最小值
题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。
示例1
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例2
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
题解01 参考
考虑左侧比较
class Solution {
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int l = 0, r = nums.length - 1;
while(l < r){
if(nums[l] < nums[r]){
return nums[l];
}
int m =l + (r - l) / 2;
if(nums[l] > nums[m]){
r = m;
}else{
l = m + 1;
}
}
return nums[l];
}
}
题解02 参考
考虑右侧比较
class Solution {
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while(l < h){
int m = l + (h - l) / 2;
if(nums[h] > nums[m]){
h = m;
}else if(nums[h] < nums[m]){
l = m + 1;
}
}
return nums[l];
}
}
总结
二分查找的应用条件是有序序列，然而当前序列并非是有序的，首先想到的就是序列重排，或者以O(n)的时间复杂度线性查找，但是显然这道题的目的并非如此。
然后，通过看题解，发现用的是二分查找，然后各种不明白全都涌上来了【菜鸡的悲哀】
- 二分查找用到的是有序序列，为什么当前的序列只是局部有序也可以适用呢？
- 二分查找通常有一个target，用来比较判断哪个区间该缩小，可是该题的target没有啊
- 二分查找通常返回的是具体的某个查找对象，最小值在其中又是如何理解的呢？
在本题中，数组的旋转是可以看成两个有序序列的拼接，那么在搜索的过程中，可能出现的情况是前面有序或者后面有序，例如二分查找搜索局部有序数组中所描述的例子，
假如：
nums = [4,5,6,7,0,1,2]，则为情况1；
nums = [6,7,0,1,2,4,5]，则为情况2；
此外，本题还可以理解为求解两个有序数组的拼结点，因为最小值一定是这个拼结点所在的地方，如果没有拼结点的话，那么就说明这是一个完整的有序数组。
因为其比较可以选择左端或者右端的值，所以分开进行讨论一下。
首先，比较nums[left]和nums[mid]的情况。
在比较之前，可以先行对整个区间进行判断，如果当前区间存在nums[left] < nums[right]的情况，那么说明收敛的区间当前有序，那么直接返回收敛的最小值nums[left]即可。而这一步在与左侧进行比较的时候是必须的，因为只有在此基础上，才可以谈当nums[left] == nums[mid]的情况。
情况一
假设nums[mid] < nums[left]，说明最小值应该在[left, mid]之间，也可以说明拼结点就在其中，此时右侧的[mid,right]一定是有序的。此外，考虑到nums[mid]可能为最小值的情况，所以right 被赋值为mid。情况二
假设nums[mid] > nums[left], 如果当前是拼接，说明最小值(mid, right]之间，可以看出此时[left, mid]中间是连续的，所以拼结点必在后一段。那么此时，nums[mid]肯定不是最小值了，所以可以越过mid，将left赋值为mid + 1。情况三
假设nums[mid] == nums[left]，虽然说题目有说不包含重复数字，这种情况通常是不需要考虑的，但是如果真正运行的时候是通过不了的，例如{2,1}这种情况，mid在开始的时候与left的值相同，都是0，而且在之后的循环中，是不满足上面的任何一种情况的，也就是说l和r的值都是无法更改的，那么就会进入到死循环的状态了。
综上，从左端考虑的时候，因为mid求值会偏向左方，所以考虑mid与left相等的情况，首先在考虑完情况二的第一种情况后，也就是保证了该序列一定不是完整的有序数组的情况下，可以肯定拼结点在后面，所以此时的left赋值mid + 1。
此外，除了上述的情况讨论，还有二分查找特有的细节难点还需要仔细考虑一下，如：
1. while循环是否需要添加等号?
可以看出while的结束条件是left == right。按照之前的分析，此时缺少了一种情况，也就是当left == right == mid的时候，如果假设此时存在这种情况，考虑数组[1]，此时进入状态三，也就是left = mid + 1，之后就跳出循环，返回nums[left]，但是此时left == 1，超出数组大小，报错。
考虑当left == right的情况下，也就是将搜索区间已经缩小到了left和right之间，如果继续的话，left会超出区间范围，即left == right的时候已经确定了一个最小值，所以此时不用再往下继续。与之前不同，也是因为题目的目的不同，该题的最终目标是求最小值，除了在中途查找到目标值之外，就是当区间收敛到只有一个值的时候，该值就是目标值，而不用像查找具体值那样，还要看最后left == right的值是否就是最终的target。
2. 返回的值为什么是nums[left]?
因为最终的终止条件是left == right，所以返回nums[right]也是一样的
下面就是从端点的右侧进行比较，同样从一下几种情况进行考虑：
情况一
假设nums[mid] < nums[right]，说明后一段连续递增，拼结点应该在[left, mid)之间，所以将right赋值为mid;情况二
假设nums[mid] > nums[right]，说明前一段连续递增，拼结点应该在(mid, right]之间，所以将left赋值为mid + 1;情况三
假设nums[mid] == nums[right]，说明只可能在left == right == mid的情况下出现，但是在此时，这么比较是没有意义的。所以不考虑这种情况。
二分查找一般的比较原则有：
- 如果有目标值target，那么直接让arr[mid] 和 target 比较即可。
- 如果没有目标值，一般可以考虑 端点
二分查找适合的场景：
- 数组有序和局部有序
局部有序也可以使用二分查找的原因，个人猜想可能在于其中求解的目的是不同的，此时并不是去找到一个具体的target，而是利用二分查找去查找例如最值这类的值，主要的是利用二分查找能够缩小查找区间的特性。
02-寻找旋转排序数组中的最小值2
剑值offer——牛客网
154. 寻找旋转排序数组中的最小值 II
本题和上题的区别在于非递减排序的数组，所以可能会有重复数据的情况，比如
- [2, 1, 2, 2, 3, 3, 3]，最小值在[left, mid]中间
- [2, 2, 2, 2, 3, 1, 2], 最小值在[mid, right]中间
所以此时并不能够定位到拼结点是在哪一块，那么此时最好的方法就是将right值减一，防止错过最小值的区间。
class Solution {
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[left] < nums[right]){
return nums[left];
}
if(nums[right] < nums[mid]){
left = mid + 1;
}else if(nums[right] > nums[mid]){
right = mid;
}else if(nums[right] == nums[mid]){
right = right - 1;
}
}
return nums[left];
}
}
这边的nums[left] < nums[right]并非是必须的，只是能够加快判断速度的作用。因为在相等的情况下具有不确定性。
最后，本文如果有什么思考错误的地方，欢迎指出！
