专题一【二分查找】(1)
模板请参考:二分查找模板
二分查找:在一个区间内,有一半是满足某一性质的,另一半是不满足这个性质的,所以我们可以使用二分查找,找到这两段区间的间断点。
本周题目:
34. 在排序数组中查找元素的第一个和最后一个位置
35. 搜索插入位置
74. 搜索二维矩阵
69. x的平方根
153. 寻找旋转排序数组中的最小值
题目思路
34. 在排序数组中查找元素的第一个和最后一个位置
给定target,找到有序数组中值等于target的区间范围,所以我们要找的是数组中大于等于target的第一个元素的位置和小于等于target的最后一个元素的位置。两次二分即可。
35. 搜索插入位置
找到一个值在有序数组中插入的位置,就是找到这个数组中第一个大于等于这个数的元素位置。
如果要使用模板的话,我们可以将二分的范围设置为0 ~ n, 因为我们的mid = (l + r) / 2,所以只有当l = r = n的时候mid=n,而这样也就退出了循环。这样n这个位置就相当于一个虚拟的哨兵,如果数组中元素都小于target的话,数组中没有大于等于target的数,l和r二分后就会等于n,那么我们就将这个数插入到数组的末尾,也就是n这个位置上。
74. 搜索二维矩阵
这道题给的是一个有序的二维数组,我们只需要将一维坐标映射到二维坐标即可。具体做法是,假设矩阵是m * n的,那么给定一个坐标x,其在二维矩阵中的坐标就是(x / n, x % n)
69. x的平方根
给定一个正整数x,让我们找到 $\lfloor sqrt(x) \rfloor$, 所以问题就是二分出0~x中小于等于$sqrt(x)$的最大的那个数。
153. 寻找旋转排序数组中的最小值
将一个升序数组在某一点进行旋转,使其前半部分移至后半部分,两个部分依然升序。如果数组进行的旋转,那么这个数组的前半部分必然是大于等于nums[0]的,而后半部分必然是小于nums[0]的,所以我们只要二分出第一个小于nums[0]的数即可。
与35题相似,如果数组没有进行翻转,也就是说这个数组是完全升序的,那么我们同样可以将二分的范围设置为0 ~ n, 这样因为数组中没有小于nums[0]的数,二分之后l = r = n,返回nums[0]即可。
代码
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
vector<int> res;
// 二分出大于等于target的第一个数的位置。
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 如果nums[l] == target则存储答案,如果nums[l] > target,则数组中没有target这个数。
if(nums[l] == target) res.push_back(l);
l = 0, r = n - 1;
while(l < r){
int mid = (l + r + 1) / 2;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
// 同上
if(nums[l] == target) res.push_back(l);
// 如果数组中没有target这个数,则返回{-1, -1}
if(res.empty()) res = {-1, -1};
return res;
}
};
35. 搜索插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// 注意这里设置的范围,如果nums[i] != target, 则二分后 l = r = nums.size()
int l = 0, r = nums.size();
// 二分出大于等于target的第一个数
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
74. 搜索二维矩阵
class Solution {
public:
typedef pair<int, int> PII;
int n, m;
// 坐标转换
PII change(int x){
return {x / m, x % m};
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
n = matrix.size(), m = matrix[0].size();
int l = 0, r = n * m - 1;
// 二分出大于等于target的第一个数
while(l < r){
int mid = (l + r) / 2;
// 坐标转换
auto t = change(mid);
if(matrix[t.first][t.second] >= target) r = mid;
else l = mid + 1;
}
auto t = change(l);
// 如果二分出来的数等于target,则返回true;否则返回false
return matrix[t.first][t.second] == target;
}
};
69. x的平方根
class Solution {
public:
int mySqrt(int x) {
long long l = 0, r = x;
// 二分出a,a^2 <= x的最大的数
while(l < r){
long long mid = (l + r + 1) / 2;
// 注意这里使用了除法,防止mid * mid溢出int的范围
if(mid <= x / mid) l = mid;
else r = mid - 1;
}
return l;
}
};
153. 寻找旋转排序数组中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
// 注意这里的范围,我们要二分的是小于nums[0]的第一个数
int l = 0, r = n;
while(l < r){
int mid = (l + r) / 2;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
// 如果数组升序,则不存在这样的数,l = r = nums.size(),nums[0]就是数组中最小的数
if(r == n) return nums[0];
return nums[l];
}
};