二分查找算法
概念
二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为O(n)的数组，二分查找的时间复杂度为O(logn)。
举例来说，给定一个排好序的数组{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等语言的习惯）或左闭右闭（便于处理边界条件），尽量只保持这一种写法；第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。
二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。
求开方
69.x的平方根
题解：
我们可以把这道题想象成，给定一个非负整数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]进行二分查找。我们使用了左闭右闭的写法。
publicintmySqrt(inta){
if(a==0)return0;
intl=1,r=a;
while(l intmid=l+r>>1; if(a/mid>=mid&&a/(mid+1)<(mid+1)){ l=mid; break; } if(a/mid>mid)l=mid+1; elser=mid-1; } returnl; } 另外，这道题还有一种更快的算法——牛顿迭代法，其公式为Xn+1=Xn−f(xn)/f′(xn)。给定f(x)=x^2−a=0，这里的迭代公式为Xn+1=(Xn+a/Xn)/2，其代码如下。 publicintmySqrt(inta){ longx=a; while(x*x>a)x=(x+a/x)/2; return(int)x; } 查找区间 34.在排序数组中查找元素的第一个和最后一个位置 题解 这道题可以看作是自己用Java实现C++里的lower_bound和upper_bound函数。这里我们尝试用左闭右开的写法，当然左闭右闭也可以。 int[]res={-1,-1}; intl=0,r=nums.length-1; booleanflag=false; while(l<=r){ intmid=l+r>>>1; if(nums[mid]>target)r=mid-1; elseif(nums[mid] else{ r=mid-1; flag=true; } } if(flag)res[0]=l; l=0; r=nums.length-1; while(l<=r){ intmid=l+r>>>1; if(nums[mid] elseif(nums[mid]>target)r=mid-1; elsel=mid+1; } if(flag)res[1]=l-1; returnres; } 旋转数组查找数字 81.搜索旋转排序数组II 题解： 即使数组被旋转过，我们仍然可以利用这个数组的递增性，使用二分查找。对于当前的中点，如果它指向的值小于等于右端，那么说明右区间是排好序的；反之，那么说明左区间是排好序的。如果目标值位于排好序的区间内，我们可以对这个区间继续二分查找；反之，我们对于另一半区间继续二分查找。 注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。在这种情况下，我们可以简单地将左端点右移一位，然后继续进行二分查找。 publicbooleansearch(int[]nums,inttarget){ intl=0; intr=nums.length-1; while(l<=r){ intmid=l+r>>1; if(nums[mid]==target)returntrue; while(nums[mid]==nums[r]&&r>mid)--r; if(nums[mid]<=nums[r]){ //说明当前数右边是排好序的递增序列 if(nums[mid] elser=mid-1; }else{ //说明当前数左边是排好序的自增序列 if(nums[mid]>target&&nums[l]<=target)returnArrays.binarySearch(nums,l,mid,target)<0?false:true; elsel=mid+1; } } returnfalse; } 练习 基础难度 154.FindMinimuminRotatedSortedArrayII(Medium) 旋转数组的变形题之一。 540.SingleElementinaSortedArray(Medium) 在出现独立数之前和之后，奇偶位数的值发生了什么变化？ 进阶难度 4.MedianofTwoSortedArrays(Hard) 需要对两个数组同时进行二分搜索。
