【力扣Hot 100】二分查找

1. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• 104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• 104 <= target <= 104

题解

求 大于等于target的最左边的位置。

但是，如果所有值都小于target的话，target要放在整个数组后面

所以最后要特判一下，数组最后一个数是否小于target，如果小于那么要放在最后面。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l < r) {int mid = (l + r) >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}if(l == nums.size() - 1 && target > nums[l]) return l + 1;return l; }
};

2. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

!https://assets.leetcode.com/uploads/2020/10/05/mat.jpg

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

!https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/25/mat2.jpg

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

题解

先找在哪一行，再找在哪一列。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int l1 = 0, r1 = matrix.size() - 1;while(l1 < r1) {int mid = (l1 + r1 + 1) >> 1;if(matrix[mid][0] <= target) l1 = mid;else r1 = mid - 1;}int l2 = 0, r2 = matrix[0].size() - 1;while(l2 < r2) {int mid = (l2 + r2 + 1) >> 1;if(matrix[l1][mid] <= target) l2 = mid;else r2 = mid - 1;}if(matrix[l1][l2] == target) return true;return false;}
};

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• 109 <= nums[i] <= 109
• nums 是一个非递减数组
• 109 <= target <= 109

题解

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0) return {-1, -1};// 找大于等于target的第一个位置int l = 0, r = nums.size() - 1;while(l < r) {int mid = (l + r) >> 1;if(nums[mid] >= target) r = mid;else l = mid + 1;}int ans1 = l;// 如果不存在if(nums[l] != target) return {-1, -1};// 找小于等于target的第一个位置l = 0, r = nums.size() - 1;while(l < r) {int mid = (l + r + 1) >> 1;if(nums[mid] <= target) l = mid;else r = mid - 1;}return {ans1, l};}
};

4. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• 104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• 104 <= target <= 104

题解

加了判断哪边有序的一步。

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r) {int mid = (l + r + 1) >> 1;if(nums[mid] == target) return mid;// 左边为有序区间else if (nums[mid] > nums[l]) {// target 在左边if(target < nums[mid] && target >= nums[l]) r = mid - 1;// target 在右边else l = mid + 1;// 右边为有序区间} else {// target 在右边if(target > nums[mid] && target <= nums[r]) l = mid + 1;// target 在左边else r = mid - 1;}}return -1;}
};

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

已知一个长度为

n

的数组，预先按照升序排列，经由

1

到

n

次

旋转

后，得到输入数组。例如，原数组

nums = [0,1,2,4,5,6,7]

在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• 5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

题解

第一种情况： —>———> nums[mid] < min，更新 min = nums[mid]， r = mid - 1;

第二种情况： ————>—> nums[mid] > min， 更新 l = mid + 1;

class Solution {
public:int findMin(vector<int>& nums) {int min = nums[0];int l = 0, r = nums.size() - 1;while(l <= r) {int mid = (l + r + 1) >> 1;if(nums[mid] < min) {min = nums[mid];r = mid - 1;}else {l = mid + 1;}}return min;}
};