【leetcode】二分搜索题目总结

704. 二分查找

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;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}}return -1;}
};

278. 第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left = 1, right = n;while (left <= right) {int mid = left + (right - left) / 2;if (!isBadVersion(mid)) {left =  mid + 1; } else {right = mid - 1;}}return left;}
};

977. 有序数组的平方

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int len = nums.size();int left = 0, right = len - 1;vector<int> res(len);for (int i = len - 1; i >= 0; --i) {int leftVal = nums[left] * nums[left];int rightVal = nums[right] * nums[right];if (leftVal > rightVal) {res[i] = leftVal;left++;} else {res[i] = rightVal;right--;}}return res;}
};

35. 搜索插入位置

class Solution {
public:int searchInsert(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;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}}// 二分没有找到插入的位置, 那么target 一定小于 left, 从left 位置插入既能满足题解。return left;}
};

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:int leftBound(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) {right = mid - 1;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1; }}// left越界，则不存在if (left >= nums.size()) {return -1;}return nums[left] == target ? left : -1;}int rightBound(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) {left = mid + 1;} else if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1; }}// right越界，则不存在if (right < 0) {return -1;}return nums[right] == target ? right : -1;}vector<int> searchRange(vector<int>& nums, int target) {if (nums.empty()) {return vector<int>({-1, -1});}int left = leftBound(nums, target);int right = rightBound(nums, target);return vector<int>({left, right});}
};

153. 寻找旋转排序数组中的最小值

旋转排序数组需要 和 right对比

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]) {left = mid + 1;} else if (nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;}}return nums[right];}
};

33. 搜索旋转排序数组

寻找最小值的下标，分段处理，注意边界

旋转排序数组需要 和 right对比

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]) {left = mid + 1;} else if (nums[mid] > nums[right]) {left = mid + 1;} else if (nums[mid] < nums[right]) {right = mid;}}return right;}int bsearch(vector<int>& nums, int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else if (nums[mid] == target) {return mid;}}return -1;}int search(vector<int>& nums, int target) {int minIndex = findMin(nums);if (minIndex == 0) {return bsearch(nums, minIndex, nums.size() - 1, target);} else if (nums[0] < target) {return bsearch(nums, 0, minIndex - 1, target);} else if (nums[0] > target) {return bsearch(nums, minIndex, nums.size() - 1, target);} else {return 0;}}
};

直接二分查找，注意边界

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[mid] < nums[right]) {if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}} else {if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}}}return -1;}
};

74. 搜索二维矩阵

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();int low = 0, high = m * n - 1;while (low <= high) {int mid = low + (high - low) / 2;int val = matrix[mid / n][mid % n];if (val == target) {return true;} else if (val < target) {low = mid + 1;} else {high = mid - 1;}}return false;}
};

4. 寻找两个正序数组的中位数

class Solution {
public:double getKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k) {int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;if (len1 > len2) {return getKth(nums2, start2, end2, nums1, start1, end1, k);}if (len1 == 0) {return nums2[start2 + k - 1];}if (k == 1) {return min(nums1[start1], nums2[start2]);}// 每次减少k/2int mid1 = start1 + min(len1, k / 2) - 1;int mid2 = start2 + min(len2, k / 2) - 1;if (nums1[mid1] < nums2[mid2]) {return getKth(nums1, mid1 + 1, end1, nums2, start2, end2, k - (mid1 - start1 + 1));} else {return getKth(nums1, start1, end1, nums2, mid2 + 1, end2, k - (mid2 - start2 + 1));}}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int k1 = (m + n + 1) / 2;int k2 = (m + n + 2) / 2;return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, k1) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, k2)) * 0.5;}
};