文章目录
- 二分查找
- 二分查找
- 搜索插入位置 （Hot 100）
- x 的平方根
- 搜索二维矩阵（Hot 100）
- 在排序数组中查找元素的第一个和最后一个位置 （Hot 100）
- 搜索旋转排序数组 （Hot 100）
- 寻找旋转排序数组中的最小值 （Hot 100）
二分查找
二分查找
二分查找
class Solution{
public:int search(vector<int>& nums, int target){// 设定左闭右闭的区间int left = 0; int right = nums.size() - 1;while (left <= right){ // 闭区间查找，left == right依然有效，所以用<=int middle = left + (right-left) / 2; // 中值索引if (nums[middle] > target){ right = middle-1; // target在左边，更新右上限}else if (nums[middle] < target){left = middle + 1; // target在右边，更新左上限}else{return middle; // 找到target，返回下标}}return -1;}};
搜索插入位置 （Hot 100）
搜索插入位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1, ans = n;while(left <= right){ int mid = ((right - left) >> 1) + left;if(nums[mid] > target){ right = mid - 1;}else if (nums[mid] < target){left = mid + 1;}else{return mid;}}// left此时 > right// left指向的是第一个大于target的元素的索引return left;}
};x 的平方根
x 的平方根
class Solution {
public:int mySqrt(int x) {int l = 0, r = x;while (l <= r) {int mid = l + (r - l) / 2;if ((long long) mid * mid < x) { l = mid + 1;} else if ((long long) mid * mid > x) {r = mid - 1;}else{return mid;}}，// l此时 > r，向下取整return r;}
};搜索二维矩阵（Hot 100）
搜索二维矩阵
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int left = 0, right = m * n - 1;while(left <= right){int mid = (right - left >> 2) + left;int x = matrix[mid / n][mid % n];if(x < target){left = mid + 1;} else if(x > target){right = mid - 1;} else{return true;}}return false;}
};
在排序数组中查找元素的第一个和最后一个位置 （Hot 100）
在排序数组中查找元素的第一个和最后一个位置
#include <vector>
using namespace std;class Solution {
public:int binarySearch(vector<int>& nums, int target) {// 二分查找变形int left = 0, right = nums.size() - 1, ans = -1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target) {ans = mid;right = mid - 1; // 找到目标值时，继续在左半部分查找} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {// 调用binarySearch函数，查找目标值的第一个位置int first_pos = binarySearch(nums, target);if (first_pos == -1) return vector<int>{-1, -1};// 查找目标值的最后一个位置int last_pos = first_pos;while (last_pos < nums.size() && nums[last_pos] == target) last_pos++;last_pos--;return vector<int>{first_pos, last_pos};}
};
搜索旋转排序数组 （Hot 100）
搜索旋转排序数组
//定理一：只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。
//定理二：判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间。
//定理三：每次二分都会至少存在一个顺序区间。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;if (nums[left] <= nums[mid]) { // left 到 mid 是顺序区间(target >= nums[left] && target < nums[mid]) ? right = mid - 1 : left = mid + 1;// 如果target在顺序区间，修改区间右边界； 如果不在，修改搜索左边界}else { // mid 到 right 是顺序区间(target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;// 如果target在顺序区间，修改区间左边界； 如果不在，修改搜索右边界}}return -1;}
};寻找旋转排序数组中的最小值 （Hot 100）
寻找旋转排序数组中的最小值
class Solution {
public: int findMin(vector<int>& nums) { int low = 0; int high = nums.size() - 1; while (low < high) { int pivot = low + (high - low) / 2; // 如果pivot位置的值小于high位置的值，说明最小值在pivot和low之间（包括pivot） if (nums[pivot] <= nums[high]) high = pivot; // 否则，最小值在pivot和high之间（不包括pivot） else low = pivot + 1; // (nums[pivot] > nums[high])} // 当low和high相等时，说明已经找到了最小值，返回该值 return nums[high]; }
};
if (nums[pivot] < nums[high])
else:
