LeetCode Hot 100：二分查找
35. 搜索插入位置
思路 1：lower_bound
class Solution {
public:int searchInsert(vector<int>& nums, int target) {return lower_bound(nums.begin(), nums.end(), target) - nums.begin();}
};
思路 2：二分查找
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > target)right = mid - 1;else if (nums[mid] < target)left = mid + 1;elsereturn mid;}return left;}
};
74. 搜索二维矩阵
思路 1：从左下方开始查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = 0, j = n - 1;while (i < m && j >= 0) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)j--;elsei++;}return false;}
};
思路 2：从右上方开始查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int i = m - 1, j = 0;while (i >= 0 && j < n) {if (matrix[i][j] == target)return true;else if (matrix[i][j] > target)i--;elsej++;}return false;}
};
思路 3：二分查找
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = m ? matrix[0].size() : 0;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int x = mid / n, y = mid % n;if (matrix[x][y] == target)return true;else if (matrix[x][y] > target)right = mid - 1;elseleft = mid + 1;}return false;}
};
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty())return {-1, -1};int lower =lower_bound(nums.begin(), nums.end(), target) - nums.begin();if (lower == nums.size() || nums[lower] != target)return {-1, -1};int upper =upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;return {lower, upper};}
};
33. 搜索旋转排序数组
class Solution {
public:int search(vector<int>& nums, int target) {if (nums.empty())return -1;int n = nums.size();if (n == 1)return nums[0] == target ? 0 : -1;int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target)return mid;if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid])right = mid - 1;elseleft = mid + 1;} else {if (nums[n - 1] >= target && target > nums[mid])left = mid + 1;elseright = mid - 1;}}return -1;}
};
153. 寻找旋转排序数组中的最小值
class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[right])right = mid;elseleft = mid + 1;}return nums[left];}
};
4. 寻找两个正序数组的中位数
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int total = m + n;if (total % 2 == 1)return getKthElement(nums1, nums2, (total + 1) / 2);elsereturn (getKthElement(nums1, nums2, total / 2) +getKthElement(nums1, nums2, total / 2 + 1)) /2.0;}int getKthElement(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0;while (true) {// 边界情况if (index1 == m)return nums2[index2 + k - 1];if (index2 == n)return nums1[index1 + k - 1];if (k == 1)return min(nums1[index1], nums2[index2]);// 正常情况int newIndex1 = min(index1 + k / 2 - 1, m - 1);int newIndex2 = min(index2 + k / 2 - 1, n - 1);int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= newIndex1 - index1 + 1;index1 = newIndex1 + 1;} else {k -= newIndex2 - index2 + 1;index2 = newIndex2 + 1;}}}
};