LeetCode入门指南 之 二分搜索
- 2021 年 9 月 1 日
- 笔记
- leetcode, LeetCode入门指南, 算法, 面试
上图表示常用的二分查找模板：
第一种是最基础的，查找区间左右都为闭区间，比较后若不等，剩余区间都不会再包含mid；一般在不需要确定目标值的边界时，用此法即可。
第二种查找区间为左闭右开，要确定target左边界时，若nums[mid] == target，取right = mid：
int left = 0;
int right = arr.length; //注意
while (left < right) { //注意
//相比 mid = (left + right) / 2的写法可以防止越界
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
//向左查找边界
right = mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
/**
* 跳出循环时，left=right；left对应元素可能为target。
* 当target若大于所有元素，退出循环时有left=right=nums.length。故最后需要判断left是否越界以及left对应元素是否为target
*/
if (left >= arr.length) return -1; //target比所有元素都大（没找到），此时表示小于target的元素有left个
if (arr[left] != target) return -1; //（没找到）此时表示小于target的元素有left个
return left; //left为target的左边界，表示小于target的元素有left个。可知，若没找到target，left为target该顺序插入的位置。
要确定target右边界时，若nums[mid] == target，取left = mid + 1:
int left = 0;
int right = arr.length; //注意
while (left < right) { //注意
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
//向右边界查找
left = mid + 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
/**
* 跳出循环时，left=right；left - 1 对应元素可能为target（比如：只有一个target时，mid指向target，下一步会将left置为mid + 1）；
* 当target小于所有元素时有left=right=0；故最后需要判断left-1是否越界和left-1对应元素是否为target
*/
if (left - 1 < 0) return -1;
if (arr[left - 1] != target) return -1;
return left - 1;
为什么left = mid + 1 而 right = mid? 这是因为我们的查找区间始终是保持为左闭右开。
重要的来了，如果前面两种你觉得麻烦不好记忆那么你只需要记住第三种即可！第三种最为强大，查找区间左右都为闭区间，比较后若不等，剩余区间都会再包含mid，最后退出时left和right相邻，故都有可能为target。理论上绝大部分场景第三种模板都能解决。
int left = 0;
int right = arr.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
//向右边界查找；向左边界查找改为 right = mid;
left = mid;
} else if (arr[mid] < target) {
left = mid;
} else if (arr[mid] > target) {
right = mid;
}
}
//判断结果
if (arr[left] == target) {
return left;
}
if (arr[right] == target) {
return right;
}
return -1;
61 · 搜索区间
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回
[-1, -1]
使用模板二：
public class Solution {
public int[] searchRange(int[] arr, int target) {
int left = 0;
int right = arr.length; //注意左闭右开
while (left < right) { //注意
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
//向左查找边界
right = mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
int start = 0;
if (left >= arr.length) {
return new int[] {-1, -1}; //没找到
} else if (arr[left] != target) {
return new int[] {-1, -1}; //没找到
} else if (arr[left] == target) {
start = left;
}
left = 0;
right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
//向右边界查找
left = mid + 1;
} else if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid;
}
}
//这里无需判断是因为查找左边界时已经确定了target存在
int end = left - 1; //注意
return new int[] {start, end};
}
}
你能尝试用模板三解决吗？
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
使用模板三：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] == target) {
left = mid; // 查找左边界
}
}
if (nums[left] >= target) return left;
if (nums[right] >= target) return right;
// 如果 target 大于所有元素
if (target > nums[right]) return nums.length;
return 0;
}
}
使用模板二：
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length; //注意，左闭右开
while (left < right) {
int mid = left + (right - left) / 2;
//查找target的左边界
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
//target的下标（存在时）或小于target的个数
return left;
}
}
74. 搜索二维矩阵
编写一个高效的算法来判断
m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
使用模板三：将二维转换为一维
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int left = 0;
int right = m*n - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
right = mid;
} else if (matrix[row][col] < target) {
left = mid;
}
}
System.out.println(right);
if (matrix[left / n][left % n] == target) return true;
if (matrix[right / n][right % n] == target) return true;
return false;
}
}
使用模板一：
class Solution {
//将二维矩阵转化为一维数组
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int left = 0;
int right = m * n - 1; //普通二分查找，两边都闭合
while (left <= right) {
int mid = left + (right - left) / 2;
int row = mid / n;
int col = mid % n;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
right = mid - 1;
} else if (matrix[row][col] < target) {
left = mid + 1;
}
}
return false;
}
}
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有
n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用
bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用API的次数。
使用模板三：
public class Solution extends VersionControl {
//思路：T代表争取，F代表错误。给定一个序列 T T T T F F F，查找第一个F下标。二分查找，
public int firstBadVersion(int n) {
int left = 1;
int right = n; //左右都闭合
while (left + 1 < right) { //注意
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid;
}
}
if (isBadVersion(left)) {
return left;
}
return right;
}
}
使用模板二：
public class Solution extends VersionControl {
//思路：T代表争取，F代表错误。给定一个序列 T T T T F F F，查找第一个F下标。二分查找，
public int firstBadVersion(int n) {
long left = 1;
long right = (long)n + 1; //左闭右开，改为long，否则2147483647会越界
while (left < right) {
int mid = (int) (left + (right - left) / 2);
//查找左边界
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return (int)left;
}
}
153. 寻找旋转排序数组中的最小值
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
使用模板三：
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1; //左闭右开
while (left + 1 < right) { //注意
int mid = left + (right - left) / 2;
//始终拿 mid 和 right比较
//在最小值的左边
if (nums[mid] > nums[right]) {
left = mid;
//在最小值的右边
} else if (nums[mid] < nums[right]) {
right = mid;
}
//没有重复数字的情况下不会出现等于的情况
}
if (nums[left] < nums[right]) {
return nums[left];
}
return nums[right];
}
}
使用模板二：
class Solution {
public int findMin(int[] nums) {
int target = nums[nums.length - 1];
int left = 0;
int right = nums.length; //注意，左闭右开
while (left < right) {
int mid = left + (right - left) / 2;
//查找左边界
if (nums[mid] == target) { // 2 3 4 1
right = mid;
//在最小值的左边
} else if (nums[mid] > target) {
left = mid + 1;
//在最小值的右边
} else if (nums[mid] < target) {
right = mid;
}
}
return nums[left];
}
}
154. 寻找旋转排序数组中的最小值 II
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,4,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,4]- 若旋转
7次，则可以得到[0,1,4,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个可能存在 重复 元素值的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
使用模板三：
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
//相等时，你无法确定此时 mid 在最小值的左边还是右边，如：2 2 2 2 2 3 4 2
//不用担心 2 为最小值时 right-- 会漏掉最小值，此时 2 总是有一个副本，mid 或 最左侧
if (nums[mid] == nums[right]) {
right--;
//在最小值的左边
} else if (nums[mid] > nums[right]) {
left = mid;
//在最小值的右边
} else if (nums[mid] < nums[right]) {
right = mid;
}
}
if (nums[left] < nums[right]) {
return nums[left];
}
return nums[right];
}
}
33. 搜索旋转排序数组
整数数组
nums按升序排列，数组中的值 互不相同 。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你 旋转后 的数组
nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。
使用模板三：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; //左右都为闭区间
while (left + 1 < right) {
int mid = left + (right - left) / 2;
//可利用mid跟left 或 right比较从而确定 left 和 mid 或 mid 与 right那个区间是有序的
//left 和 mid间有序
if (nums[left] < nums[mid]) {
if (target >= nums[left] && target <= nums[mid]) {
right = mid;
} else {
left = mid;
}
//mid 和 right间有序
} else if (nums[mid] < nums[right]) {
if (target >= nums[mid] && target <= nums[right]) {
left = mid;
} else {
right = mid;
}
}
}
if (nums[left] == target) {
return left;
}
if (nums[right] == target) {
return right;
}
return -1;
}
}
81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组
nums，数组中的值不必互不相同。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转 ，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,4,4,5,6,6,7]在下标5处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]。给你 旋转后 的数组
nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums中存在这个目标值target，则返回true，否则返回false。
使用模板三：
class Solution {
public boolean search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; //左右都为闭区间
while (left + 1 < right) {
int mid = left + (right - left) / 2;
//可利用mid跟left 或 right比较从而确定 left 和 mid 或 mid 与 right那个区间是有序的
if (nums[left] < nums[mid]) {
if (target >= nums[left] && target <= nums[mid]) {
right = mid;
} else {
left = mid;
}
} else if (nums[mid] < nums[right]) {
if (target >= nums[mid] && target <= nums[right]) {
left = mid;
} else {
right = mid;
}
} else if (nums[left] == nums[mid]) { //与上例不同点
left++;
} else if (nums[right] == nums[mid]) { //与上例不同点
right--;
}
}
if (nums[left] == target || nums[right] == target) {
return true;
}
return false;
}
}
