当前位置：首页 > ds >正文

【LeetCode 热题 100】搜索插入位置 / 搜索旋转排序数组 / 寻找旋转排序数组中的最小值

ds 2025/5/17 7:54:05

⭐️个人主页：@小羊 ⭐️所属专栏：LeetCode 热题 100 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

搜索插入位置

搜索插入位置

在这里插入图片描述

为什么最后可以直接 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];}
};