【数据结构与算法】LeetCode：二分查找

二分查找

二分查找

二分查找

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: