二分查找算法
概念
二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(log n)。
举例来说，给定一个排好序的数组 {3,4,5,6,7}，我们希望查找 4 在不在这个数组内。第一次折半时考虑中位数 5，因为 5 大于 4, 所以如果 4 存在于这个数组，那么其必定存在于 5 左边这一半。于是我们的查找区间变成了 {3,4,5}。（注意，根据具体情况和您的刷题习惯，这里的 5 可以保留也可以不保留，并不影响时间复杂度的级别。）第二次折半时考虑新的中位数 4，正好是我们需要查找的数字。于是我们发现，对于一个长度为 5 的数组，我们只进行了 2 次查找。如果是遍历数组，最坏的情况则需要查找 5 次。
我们也可以用更加数学的方式定义二分查找。给定一个在 [a, b] 区间内的单调函数 f (x)，若f (a) 和 f (b) 正负性相反，那么必定存在一个解 c，使得 f ( c) = 0。在上个例子中，f (x) 是离散函数f (x) = x +2，查找 4 是否存在等价于求 f (x) −4 = 0 是否有离散解。因为 f (1) −4 = 3−4 = −1 < 0、f (5) − 4 = 7 − 4 = 3 > 0，且函数在区间内单调递增，因此我们可以利用二分查找求解。如果最后二分到了不能再分的情况，如只剩一个数字，且剩余区间里不存在满足条件的解，则说明不存在离散解，即 4 不在这个数组内。
具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍，第一是尝试熟练使用一种写法，比如左闭右开（满足 C++、Java等语言的习惯）或左闭右闭（便于处理边界条件），尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。
求开方
题解：
我们可以把这道题想象成，给定一个非负整数 a，求 f (x) = x^2 − a = 0 的解。因为我们只考虑 x ≥ 0，所以 f (x) 在定义域上是单调递增的。考虑到 f (0) = −a ≤ 0， f (a) = a ^2 − a ≥ 0，我们可以对 [0, a] 区间使用二分法找到 f (x) = 0 的解。
注意，在以下的代码里，为了防止除以 0，我们把 a = 0 的情况单独考虑，然后对区间 [1, a]进行二分查找。我们使用了左闭右闭的写法。
public int mySqrt(int a) {
if (a==0) return 0;
int l=1,r=a;
while(l<r){
int mid=l+r>>1;
if (a/mid>=mid&&a/(mid+1)<(mid+1)){
l=mid;
break;
}
if (a/mid>mid) l=mid+1;
else r=mid-1;
}
return l;
}另外，这道题还有一种更快的算法——牛顿迭代法，其公式为 Xn+1 = Xn − f (xn)/ f′(xn)。给定 f (x) = x^2 − a = 0，这里的迭代公式为 Xn+1 = (Xn + a/Xn)/2，其代码如下。
public int mySqrt(int a) {
long x = a;
while (x * x > a) x = (x + a / x) / 2;
return (int)x;
}查找区间
题解
这道题可以看作是自己用Java实现 C++ 里的 lower_bound 和 upper_bound 函数。这里我们尝试用左闭右开的写法，当然左闭右闭也可以。
int[] res = {-1,-1};
int l = 0,r = nums.length-1;
boolean flag = false;
while(l<=r){
int mid = l+r>>>1;
if(nums[mid] > target) r=mid-1;
else if(nums[mid] < target) l=mid+1;
else{
r=mid-1;
flag=true;
}
}
if(flag) res[0] = l;
l = 0;
r = nums.length-1;
while(l<=r){
int mid = l+r>>>1;
if(nums[mid] < target) l=mid+1;
else if(nums[mid] > target) r=mid-1;
else l=mid+1;
}
if(flag) res[1] = l-1;
return res;
}旋转数组查找数字
题解：
即使数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，如果它指向的值小于等于右端，那么说明右区间是排好序的；反之，那么说明左区间是排好序的。如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之，我们对于另一半区间继续二分查找。
注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。在这种情况下，我们可以简单地将左端点右移一位，然后继续进行二分查找。
public boolean search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
while(l<=r){
int mid = l+r>>1;
if(nums[mid]==target) return true;
while(nums[mid]==nums[r] && r>mid) --r;
if(nums[mid]<=nums[r]){
//说明 当前数右边 是排好序的递增序列
if(nums[mid]<target&&nums[r]>=target) return Arrays.binarySearch(nums,mid,r+1,target)<0?false:true;
else r = mid-1;
}else{
//说明 当前数左边 是排好序的自增序列
if(nums[mid]>target&&nums[l]<=target) return Arrays.binarySearch(nums,l,mid,target)<0?false:true;
else l = mid+1;
}
}
return false;
}练习
基础难度
154.Find Minimum in Rotated Sorted Array II (Medium)
旋转数组的变形题之一。540.Single Element in a Sorted Array (Medium)
在出现独立数之前和之后，奇偶位数的值发生了什么变化？
进阶难度
4.Median of Two Sorted Arrays (Hard)
需要对两个数组同时进行二分搜索。
