【算法】【优选算法】二分查找算法（上）

一、二分查找简介

运用场景：

• 当数组是有二段性的时候就可以使用，
• 二段性就是指：我们可以找到一个相同规律每次都能够选取一个数，将当前数组分成两段。
• 我们计算中点的时候有两种计算方法，mid = (right + left) / 2 = left + (right - left) / 2 和 mid = (right + left +1) / 2 = left + (right - left +1)。
• • 这两种方式对于奇数长度的数组来说，没区别，但是对于偶数长度来说，中点有两个点（比如长度为四的数组，中点就可以是1下标也可以是2下标），第一个就是拿到前一个中点，第二个就是拿到后一个中点。

1.1 朴素二分模板

模版：

while(left <= right) {int mid = left + (right - left) / 2;if(……) left = mid + 1;else if(……) right = mid - 1;else return ……; 
}

1.2 查找区间左端点模版

模版：

while(left < right) {int mid = left + (right - left) / 2;if(……) left = mid + 1;else right = mid; 
}

1.3 查找区间右端点模版

模版：

while(left < right) {int mid = left + (right - left + 1) / 2;if(……) left = mid; else right = mid - 1;
}

这两个模版详解在目录三的3.1题解中，也就是Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置的题解。

细节理解

• 循环条件left <= right ：这是因为，如果当前[left , right ]区间中只有一个元素的时候，我们还是需要进行比较。
• mid = left + ( right - left) / 2：这是因为，我们直接使用(left + right) / 2来求中间值，如果数组很大那么left + right的值是可能超过int的范围的，减法就没有这种风险。

二、leetcode 704.⼆分查找

题目链接：leetcode 704.⼆分查找
题目描述：

题目解析：

• 这道题就是在一个有序数组中找到一个等于目标值的元素的下标，没找到就返回-1。

2.1 二分查找

解题思路：

• 直接套用上面的朴素模版即可。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int search(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 right = mid - 1;}return -1;}
}

2.2 暴力枚举

解题思路：

• 直接遍历数组，让目标值与每一个元素相比较，如果相等，那么就返回当前下标。
• 数组遍历完，没找到相等元素，返回-1即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
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;}
}

三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置

题目链接：Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置
题目描述：

题目解析：

• 给的是一个非递减数组，意思就是这个数组中元素的值是一定大于或等于前面一个元素的。
• 返回数组中等于target的子数组的头尾下标，如果只有一个，那么该下标即是头也是尾，如果没有返回两个-1。
• 题目要求使用复杂度为O(logN)，但是其实O(N^2)和O(N)也能过。

3.1 二分查找

解题思路：

• 当我们要找的是一段区间，那么我们可以尝试分别去找左端点和右端点，这样就是一个区间了。
• 我们将数组拆分，可以以等于target来拆分，
• • 分法一：一段是 >= target的元素，一段是 < target元素，这就是求左端点的分法。
• • 分法二：一段是 <= target的元素，一段是 > target元素，这就是求右端点的分法。
• 上面两种分法，都是不断按照同一个规律，将数组拆分为两段，这就是二段性的体现。
• 求左端点：
• • 循环条件：left < right 因为我们是求的左端点，其中并不会写返回语句，当我们left和right相等的时候，我们如果还进循环，就会陷入死循环，并且其实这个时候就是我们要求的左端点了。
• • 中点的求法：mid = left + (right - left) / 2; 因为当我们只有两个节点时，求取到后一个节点作为中点时，就让mid指向right了，后续更新mid还会指向这里，陷入死循环。
• • 当mid元素 >= target的时候，因为我们求的是左端点，当前的左端点肯定在[ left , mid]区间之间，并且有可能就是mid，所以要让right指向mid。
• • 当mid元素 < target 的时候，左端点肯定在( mid , right ] 区间，所有让 left = mid + 1；
• 求右端点：
• • 循环条件：left < right 因为我们是求的右端点，其中并不会写返回语句，当我们left和right相等的时候，我们如果还进循环，就会陷入死循环，并且其实这个时候就是我们要求的右端点了。
• • 中点的求法：mid = left + (right - left + 1) / 2; 因为当我们只有两个节点时，以第一个节点为中点，求取到后面就让mid指向left了，后续更新mid还会指向这里，又陷入死循环。
• • 当mid元素 <= target的时候，因为我们求的是右端点，当前的右端点肯定在[ mid, right ]区间之间，并且有可能就是mid，所以要让left指向mid。
• • 当mid元素 > target 的时候，右端点肯定在[ left, mid ) 区间，所有让 right = mid - 1；
• 在左右端点求取之间，我们还要更新一下结果中的端点值，如果没找到端点，那么就代表给返回[-1, -1]了。
• 边界：当数组中没有元素的时候，我们去求端点的时候是会直接越界的，所以这种情况要单独处理。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[]{-1,-1};//边界if(nums.length == 0) return ret;//查找左端点int left = 0;int 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) ret[0] = left; else return ret;//查找右端点right = nums.length-1;while(left < right) {int mid = left + (right-left+1)/2;if(nums[mid] > target) right = mid -1;else left = mid;}ret[1] = left;return ret;}
}

3.2 暴力枚举

解题思路：

• 我们直接一个for循环，遍历数组，当遇到等于目标值的时候，再一层for循环遍历区间尾即可。

解题代码：

//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[]{-1,-1};for(int i = 0; i < nums.length; i++) {if(nums[i] == target) {ret[0] = i;for(int j = i; j < nums.length ;j++) {if(j+1 >= nums.length || nums[j+1] > target) {ret[1] = j;return ret;}}}}return ret;}
}

优化：

• 我们可以借助滑动窗口的思想，
• 当我们遇到等于目标值的元素之后，并且left还是初始值的时候，我们就可以将ret[ 0 ]更新。
• 每次right遇到等于目标值的元素的时候，就更新ret[ 1 ]。

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret = new int[]{-1,-1};for(int left = -1,right = 0; right < nums.length; right++) {if(nums[right] == target) {ret[1] = right;if(left == -1) {left = right;ret[0] = right;}}if(nums[right] > target) break;}return ret;}
}

四、35.搜索插⼊位置

题目链接：35.搜索插⼊位置
题目描述：

题目解析：

• 数组是升序的，当数组中有等于target，返回该元素下标。
• 如果没有，返回比他小的最近元素的下一个下标。

4.1 二分查找

解题思路：

• 套用上面求左右端点的模版都可以求。
• 有一种边界情况没有求，也就是示例3的情况。单独考虑。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int searchInsert(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) left = mid + 1;else right = mid;}if(nums[right] >= target) return right;return right+1;}
}class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left + 1) / 2;if(nums[mid] > target) right = mid - 1;else left = mid;}if(nums[right] >= target) return right;return right+1;}
}

4.2 暴力枚举

解题思路：

• 直接遍历数组。
• 处理边界情况，插入0位置或者插入数组尾。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int searchInsert(int[] nums, int target) {for(int i = 0; i < nums.length; i++) {if(nums[i] == target) return i;if(nums[i] < target && i < nums.length - 1 && nums[i+1] > target) return i+1;}  if(nums[0] >= target) return 0; return nums.length;}
}

五、69.x的平⽅根

题目链接：69.x的平⽅根
题目描述：

题目解析：

• 求一个数的算术平方根，向下取整。

4.1 二分查找

解题思路：

• 我们可以将 1 - x 的数分为两个区间：小于x算术平方根的区间，大于等于算术平方根的区间。
• 因为我们需要求的是小于等于算术平方根的最大值，所以相当于求右端点。
• 套用模版，处理一下边界情况即可。
• 因为这道题的x范围是整个int，所以当我们求平方的时候是可能超出int范围的，所以我们使用long。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int mySqrt(int x) {long left = 1;long right = x;//边界情况if(x <= 1) return x;while(left < right) {long mid = left + (right - left + 1) / 2;if(mid * mid <= x) left = mid;else right = mid - 1;}return (int)left;}
}

4.2 暴力枚举

解题思路：直接使用一个for循环，将0 到x 的数遍历，看是否符合要求即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int mySqrt(int x) {for(long i = 0; i <= x; i++) {if(i * i == x) return (int)i;else if(i * i < x && (i+1) * (i+1) > x) return (int)i;}return 0;}
}