二分查找1

1. 二分查找（704）

题目描述：

算法原理：
暴力解法就是遍历数组来找到相应的元素，使用二分查找的解法就是每次在数组中选定一个元素来将数组划分为两部分，然后因为数组有序，所以通过大小关系舍弃一部分数组，最终不断重复这个过程完成查找，时间复杂度可以达到logN。
代码如下：

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while (right >= left) {int mid = left + (right - left) / 2;if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else {return mid;}}return -1;}
}

题目链接

2. 在排序数组中查找元素的第一个和最后一个位置（34）

题目描述：

朴素二分查找：
这题我们可以先使用朴素二分查找的方法取找到等于target的元素下标，此时再分别使用两个循环去比较左右两边元素是否与target相等，如果相等则分别向左和向右移动，最终返回对应的下标即可，这个过程很好理解。
代码如下：

class Solution {public int[] searchRange(int[] nums, int target) {int left = 0, right = nums.length - 1;int index1 = -1, index2 = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {index1 = mid;index2 = mid;while (index1 - 1 >= 0 && nums[index1] == nums[index1 - 1]) {index1--;}while (index2 + 1 < nums.length && nums[index2] == nums[index2 + 1]) {index2++;}break;}}return new int[] { index1, index2 };}
}

优化朴素二分查找：
首先我们去寻找target的左边界，为了便于理解我们给出图1，数组的元素可以分为两个部分，前半部分是小于target的元素，后一部分是大于等于target的部分。
图1

如图2，当我们的nums[mid]也就是x落入前半部分的时候，为了去接近target需要使得left=mid+1，当我们的x落入后半部分的时候，此时我们不能够使right=mid-1，因为如果说此时x是等于target的并且是左边的最后一个target，那么将right-1后面就直接再也找不到正确的target了。综上，如果x落入图1的第二段区间，那么就使得right=mid。很好理解的一点就是通过这样的操作，left在不断的向右移动，right在不断的向左移动但是它的下标也不会超出图1第二段区间的左边，这样我们就能够找到连续target的左边界。
图2

然后我们来处理两个细节问题，第一个问题就是这样使用二分查找，它的循环条件是使用left<right还是left<=right。我们朴素二分查找是使用后者的，但是在这里要使用前者。为什么呢，这里先分三种情况：
（1）target在right和left区间之内
在这种情况下，最终right会等于left，此时跳出循环即可，直接得到的下标就是正确答案，根本不需要去额外在循环当中去分三种情况> < ==。
（2）left和right区间内都是小于target的
此时left不断的加一最终和right相等跳出循环即可，然后判断nums[right]是否等于target。
（3）left和right区间内都是大于target
此时right不断向右最终和left相等跳出循环。
以上是选择left<right的原因之一，另一个原因就是使用left<=right会造成死循环，当我们使用图2中的方法来处理最终得到结果时，此时left等于right，如果使用left<=right下一次不会跳出而是会进入死循环，这一点还是很好理解的。
综上三种情况，我们使用left<right这样的循环条件，是因为当跳出循环时我们可以进行判断nums[right]是否等于target从而直接得到结果，另外可以防止死循环。
第二个细节问题就是中点的选择，一般是有两种方式来计算中点如图3。
图3

图3中两种计算中点的方式在朴素二分查找中都是可以适用的，但是这里也就是按照图2的计算方式来说两种方式是有差别的，如果我们使用第二种计算方式，如果我们将left和right的区间缩小到两个元素，也就是left+1等于right这种情况，此时mid计算为right，nums[mid]等于target，right=mid，后面的循环mid经过计算又等于原来的值，由此进入死循环，为了避免这种情况我们就需要使用第一种计算中点的方式。
以上就是求连续的target左边界的分析，对于右边界的分析也是类似的，唯一需要注意的就是此时计算中点的方式要选择第二种否则会造成死循环。
优化后代码如下：

class Solution {public int[] searchRange(int[] nums, int target) {int left1 = 0, right1 = nums.length - 1;if (right1 == -1) {return new int[] { -1, -1 };}int[] ret = new int[2];while (left1 < right1) {int mid1 = left1 + (right1 - left1) / 2;if (nums[mid1] < target) {left1 = mid1 + 1;} else {right1 = mid1;}}if (nums[right1] == target) {ret[0] = right1;} else {ret[0] = -1;}int left2 = 0, right2 = nums.length - 1;while (left2 < right2) {int mid2 = left2 + (right2 - left2 + 1) / 2;if (nums[mid2] > target) {right2 = mid2 - 1;} else {left2 = mid2;}}if (nums[left2] == target) {ret[1] = left2;} else {ret[1] = -1;}return ret;}
}

解题模板：

下面出现减一上面就需要加一。
题目链接

3. 搜索插入位置（35）

题目描述：

算法原理：
根据题目知道，这里的数组是一个升序并且无重复元素的数组，并且如果数组内包含target就求出target的下标，如果数组中不包含target就求出第一个大于target的数的下标，这就是题目的要求。那么我们就可以将数组分为两部分，第一部分是小于target的部分，第二个部分是大于等于target的部分，那么我们直接求出第二部分的左边界即可。前面的题目我们也给出了模板以及解题的思路，具体看代码。
代码如下：

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;if (nums[right] < target) {return right + 1;}while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return right;}
}

题目链接

4. x 的平方根 （69）

题目描述：

算法原理：
根据题目我们知道可以将1到x就当成数组中的数，然后我们需要去找到一个数n去满足n*n等于x，这个n就可以使用二分查找来进行寻找，将1到x分为两部分，一部分是数的平方小于等于x另一部分是数的平方大于x，显然我们只需要找到第一部分的右边界即可。不过这题提交的时候要注意数据溢出的问题，要确定好数的类型。
代码如下：

class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}int right = x, left = 1;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid <= x) {left = (int) mid;} else {right = (int) mid - 1;}}return left;}
}

题目链接