【Hot100】二分查找
系列文章目录
文章目录
- 系列文章目录
- 方法论
- 0、二分查找框架
- 1、查找一个数
- 2、寻找左侧边界
- 3、寻找右侧边界
- 4、二分查找代码模版
- Hot100 题单的二分查找
- 35. 搜索插入位置
- 74. 搜索二维矩阵
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 33. 搜索旋转排序数组
方法论
0、二分查找框架
int binarySearch(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (...) {int mid = left + (right - left) / 2;if (nums[mid] == target) {...} else if (nums[mid] < target) {left = ...} else if (nums[mid] > target) {right = ...}}
}
计算 mid 时需要防止溢出，如果 left 和 right 太大，直接相加有可能导致溢出的情况。所以代码中使用 left + (right - left) / 2 来代替 (left + right) / 2，两者的运算结果是相同的。
最好不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
1、查找一个数
这个场景是最简单的，即搜索一个数，如果存在，返回其索引，否则返回 -1。
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 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 if (nums[mid] > target) {right = mid - 1;}}return -1;}
};
- 为什么 while 循环的条件是
<=而不是<？right的初始赋值是nums.size() - 1，最后一个元素的索引，相当于闭区间[left, right]。什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：if(nums[mid] == target)return mid;但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间
[left, right]为空的时候应该终止。
当left 等于 right时，搜索区间还有一个元素，则 while 循环还应该继续执行，所以循环条件要包含相等的情况。只有当left大于right时，循环才会终止。 - 为什么是
left = mid + 1，right = mid - 1？代码中，搜索区间是两端都闭合的
[left, right]。那么当发现索引mid不是要找的target时，下一步应该去搜索哪里呢？当然是去搜索区间[left, mid-1]或者区间[mid+1, right]，因为 mid 已经搜索过，应该从搜索区间中去除。
算法的缺陷
比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
2、寻找左侧边界
以下是最常见的代码形式：
int left_bound(int[] nums, int target) {int left = 0, right = nums.length - 1;// 搜索区间为 [left, right]while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 搜索区间变为 [mid+1, right]} else if (nums[mid] > target) {right = mid - 1; // 搜索区间变为 [left, mid-1]} else if (nums[mid] == target) {// 因为找的是左侧边界，所以收缩去掉右搜索区间right = mid - 1;}}// 判断 target 是否存在于 nums 中。如果越界，则 target 不存在，返回 -1if (left < 0 || left >= nums.length) return -1;// 判断一下 nums[left] 是不是 targetreturn nums[left] == target ? left : -1;
}
-
为什么该算法能够搜索左侧边界？
关键在于对于
nums[mid] == target这种情况的处理：if (nums[mid] == target) right = mid - 1;找到 target 时没有立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
-
while 循环结束后
left的情况a. 当
target存在于数组中，left会指向第一个target
b. 当数组中不存在target
(1) 当target比数组中所有元素都大时，left会等于nums.size()，left会越界
(2) 当target比数组中所有元素都小时，left会等于0，left不会越界
(3) 数组中有比target大的元素，left指向第一个大于target的元素
因此需要循环体结束后，需要判断left是否越界，nums[left]是否为目标值。
3、寻找右侧边界
int right_bound(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 if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {// 这里改成收缩左侧边界即可left = mid + 1;}}// 最后改成返回 rightif (right < 0 || right >= nums.length) {return -1;}return nums[right] == target ? right : -1;
}
- while 循环结束后
right的情况a. 当
target存在于数组中，left会指向最后一个target
b. 当数组中不存在target
(1) 当target比数组中所有元素都小时，right会等于-1，right会越界
(2) 当target比数组中所有元素都大时，right会等于数组最后一个元素的索引，right不会越界
(3) 数组中有比target小的元素，left指向最后一个小于target的元素
4、二分查找代码模版
int binary_search(vector<int>& nums, int target) {int left = 0, right = nums.size()-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 if(nums[mid] == target) {return mid; // 直接返回}}return -1; // 直接返回
}int left_bound(vector<int>& nums, int target) {int left = 0, right = nums.size()-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 if (nums[mid] == target) {// 别返回，锁定左侧边界，收缩右侧边界right = mid - 1;}}// 如果 target 大于 nums 中的所有数，left 会等于nums.szie()，会越界if (left < 0 || left >= nums.size()) return -1;// 判断一下 nums[left] 是不是 targetreturn nums[left] == target ? left : -1;
}int right_bound(vector<int>& nums, int target) {int left = 0, right = nums.size()-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 if (nums[mid] == target) {// 别返回，锁定右侧边界，收缩左侧边界left = mid + 1;}}// 如果 target 小于 nums 中的所有数，right 会等于 -1，会越界if (right < 0 || right >= nums.size()) return -1;return nums[right] == target ? right : -1;
}
Hot100 题单的二分查找
35. 搜索插入位置
35. 搜索插入位置： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2: 输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3: 输入: nums = [1,3,5,6], target = 7 输出: 4
分析：
根据示例，可以看出插入的位置有以下几种情况：
(1)当target在数组中存在时，那么数组中第一个target元素的索引，即为要插入的位置;
(2)当target在数组中不存在时，那么数组中第一个大于target元素的索引，即为要插入的位置;
因此，可以利用寻找左侧边界的模版代码，来解决这道题。
答案：
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size()-1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > target)right = mid - 1;else if(nums[mid] < target)left = mid + 1;else if(nums[mid] == target)right = mid - 1;}return left;}
};
74. 搜索二维矩阵
74. 搜索二维矩阵：给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
>
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
分析：
可以将二维看成一维的来做，若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
假设二维矩阵的形状为nnn x mmm，一维中，下标为i，对应再二维矩阵中的坐标为：(i/m, i%m。
答案：
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n = matrix.size(), m = matrix[0].size();int left = 0, right = n*m-1;while(left <= right){int mid = left + (right - left) / 2;int row = mid/m, col = mid%m;if(target > matrix[row][col])left = mid + 1;else if(target < matrix[row][col])right = mid - 1;else if(target == matrix[row][col])return true;}return false;}
};