优选算法的折半之智：二分查找专题(一)
专栏：算法的魔法世界
个人主页：手握风云
目录
一、二分查找算法
可能很多老铁在之前可能接触过朴素的二分查找思想，比如在一个有序数组中找到目标值。但二分查找算法不仅仅局限于数组有序的场景下，只要一个数组里面符合“二段性”，当数组中间的某一个值不符合要求，我们就可以把这个值左区间或者右区间舍去，再去另一个区间进行查找。这个“二段性”，并不一定从中间划分，也可以1/3、1/4出开始划分。但我们大部分还是选择从中间划分，因为从概率学角度讲，中间划分是数学期望最高的。二分查找算法细节特别多，也特别容易写出死循环。但我们要理解了算法原理和二分查找的模板，那么就非常简单了。
二、例题讲解
2.1. 二分查找
对于上面的题，我们可以先使用暴力解法，利用for循环遍历数组中的每一个元素来找到目标值，这个算法的时间复杂度为
。
class Solution { public int search(int[] nums, int target) { for(int i = 0;i < nums.length;i++){ if(nums[i] == target){ return i; } } return -1; } }接下来对这个算法进行优化，我们先设x = (right + left)/2。如果nums[x] > target，那么left = x+1；如果nums[x] < target，那么right = x-1；如果nums[x] = target，直接返回x，循环走下来找不到，返回-1。
有些细节我们需要注意一下：1.循环结束的条件是什么？当x与目标值进行比较时，left可以移动到x右边，那么x的左边已经判断过了都是小于目标值，但右边还是未知的，即使left与right相遇，那这个数依然是未知的。所以循环结束的条件是left>right，而不是left==right。2.为什么二分查找是正确的？二分查找虽然不像上面的暴力解法一个一个比较，但我们利用“二段性”以及数组的有序性，只比较一个数字就排除一半的区间。3.二分查找的时间复杂度。当我们的循环执行一次时，将区间划分为
；循环执行两次时将区间划分为
；循环执行三次时将区间划分为
……最坏情况下left与right相遇，将区间划分为1，则
，时间复杂度为
。
完整代码实现：
class Solution { public int search(int[] nums, int target) { int left = 0,right = nums.length-1; while(left <= right){ int mid = (left + right)/2; if(nums[mid] > target) right = mid -1; else if(nums[mid] < target) left = mid +1; else return mid; } return -1; } } while(left <= right){ int mid = left + (right - left) / 2; if(nums[……) right = mid -1; else if(……) left = mid +1; else return mid; }2.2. 在排序数组中查找元素的第一个和最后一个位置
我们的暴力解法，就是去从前往后遍历数组，找出起始位置用begin记录，然后找出结束位置用end记录，最终返回[begin,end]。很明显，暴力解法的时间复杂度为
。
我们还是根据数组有序的特性，来利用二分查找进行优化。这里我们不能使用上面的朴素二分查找，因为找出的中间值无法确定是不是起始位置或者结束位置，我们向左和向右遍历数组找出起始与结束，所以时间复杂度依然是
。所以朴素的二分查找不能解决问题。
我们还是要回归到二分查找的本质，“二段性”。我们先来查找区间的左端点，我们假设中间下标mid对应值的值为x，让x与target进行比较。如果x小于target，说明mid位于左边的区间，让left = mid+1；如果x大于等于target（这里等于的时候，并不一定是最终位置），说明mid位于右边的区间，让right=mid（因为mid指向的位置有可能正好是左区间）。
我们需要处理一下细节：1.循环条件。right指针移动的时候，一直是在合法的区间，left一直想要跳出这个不合法的区间，直到两个指针相遇，无需判断，相遇的位置就是我们要找的结果。并且如果left=right，一直处于x>=t的条件，而right指针又不会移动，就会陷入死循环。
2.找出中点操作。中点有两种求法，mid=left+(right-left)/2或者是mid=left+(right-left+1)/2。如果数组元素个数为偶数个，按照第二种求法，mid就会落在右边，又会陷入死循环，所以我们需要选择第一种求法。
接下来是查找区间的右端点，与上面的查找左端点的方法大同小异，只是细节的处理不一样。我们要划分的区间为小于等于target与大于tareget两部分，求中点的方式要采用第二种，防止mid落在左边的元素造成死循环。
完整代码实现：
class Solution { public int[] searchRange(int[] nums, int target) { int[] ret = new int[2]; ret[0] = ret[1] = -1; //处理边界情况 if (nums.length == 0) return ret; //查找左端点 int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } //判断是否有结果 if (nums[left] != target) return ret; else ret[0] = right; //二分右端点 left = 0; right = nums.length - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (nums[mid] <= target) left = mid; else right = mid - 1; } ret[1] = left; return ret; } }模板总结：
//查找左端点 while (left < right) { int mid = left + (right - left) / 2; if (……) left = mid + 1; else right = mid; } //查找右端点 while (left < right) { int mid = left + (right - left + 1) / 2; if (……) left = mid; else right = mid - 1; }2.3. x 的平方根
题目要求不适用内置函数求平方根，我们需要自己写一个算法来求平方根。如果求出的平方根是小数，则舍去小数部分。
我们先来思考暴力解法：由于x是非负整数，那么x的平方根定义是小于等于x的。其中0和1的平方根都为它本身。如果x=17，我们可以从1开始向右枚举，如果找到一个数n，n*n小于等于x，且(n+1)*(n+1)大于x，则x的平方根则为n。
我们可以直接套用上面的模板。如果mid * mid <= x，则left=mid； 如果mid * mid > x，则right=mid+1。这里还有一点需要注意，mid*mid可能会因为数据太大造成溢出，所以mid用long来创建。
完整代码实现：
class Solution { public int mySqrt(int x) { if(x == 0) return 0; long left = 1,right = x; while(left < right){ long mid = left + (right-left+1)/2; if(mid * mid <= x) left = mid; else right = mid-1; } return (int)left; } }2.4. 搜索插入位置
通过上面的示例分析，插入结果分为两种：1.插入第一个大于等于target前的位置；2.插入数组的末尾。很明显，我们可以按照查找区间左端点的模板来解决。我们还需要判断一下示例3这种情况，也就是插入数组的末尾。
完整代码实现：
class Solution { public int searchInsert(int[] nums, int target) { int left = 0,right = nums.length-1; while(left < right){ int mid = left + (right - left)/2; if(nums[mid] < target) left = mid+1; else right = mid; } if(nums[left] < target) return left+1; return left; } }
