搜索插入位置
为什么最后可以直接 return l，如果没找到目标值，则会由 l > r 出循环。如果是由 r = mid - 1 出的循环，说明此时 mid == l 且所指位置就是要插入的位置；如果是由 l = mid + 1 出的循环，mid所指的元素刚好小于目标值，则出循环后l所指的就是需要插入的位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (nums[mid] > target) r = mid - 1;
else if (nums[mid] < target) l = mid + 1;
else return mid;
}
return l;
}
};
搜索二维矩阵
每行进行一次二分查找。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m; i++)
{
int l = 0, r = n - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (matrix[i][mid] < target) l = mid + 1;
else if (matrix[i][mid] > target) r = mid - 1;
else return true;
}
}
return false;
}
};
将二维数组看作一维数组进行二分。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int l = 0, r = m * n - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
int t = matrix[mid / n][mid % n];
if (t < target) l = mid + 1;
else if (t > target) r = mid - 1;
else return true;
}
return false;
}
};
在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
if (nums[l] != target) return {-1, -1};
int begin = l;
r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l + 1) / 2;
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
return {begin, r};
}
};
搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid])
{
if (nums[0] <= target && nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
else
{
if (target <= nums[n - 1] && nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
};
寻找旋转排序数组中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < nums[n - 1]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
