力扣hot100--＞二分查找

二分查找

1. 33. 搜索旋转排序数组

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

3. 240. 搜索二维矩阵 II

3. 287. 寻找重复数

二分查找

1. 33. 搜索旋转排序数组

中等

整数数组 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 left{}, right = nums.size() - 1; // 左右边界初始化

while (left <= right) { // 当左边界小于等于右边界时继续循环
int mid = (left + right) / 2; // 计算中间位置

if (nums[mid] == target) { // 如果找到目标值，返回索引
return mid;
}
// 判断左半部分是否有序
else if (nums[mid] >= nums[left]) {
// 如果目标值在左半部分范围内，缩小右边界
if (target <= nums[mid] && target >= nums[left]) {
right = mid - 1;
}
// 否则目标值在右半部分，缩小左边界
else {
left = mid + 1;
}
}
// 如果右半部分是有序的
else {
// 如果目标值在右半部分范围内，缩小左边界
if (target >= nums[mid] && target <= nums[right]) {
left = mid + 1;
}
// 否则目标值在左半部分，缩小右边界
else {
right = mid - 1;
}
}
}

return -1; // 如果未找到目标值，返回 -1
}
};

解释：

在旋转排序数组中，判断左右边界是否有序的作用是：

确定目标值可能在哪一部分。
依据部分有序性，快速缩小查找范围。
使二分查找在部分有序的条件下仍然有效。

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

中等

给你一个按照非递减顺序排列的整数数组 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) {
// 先找数组中第一个不小于target的元素
auto left = lower_bound(nums.begin(),nums.end(),target);
// 找数组中大于目标值的第一个元素
auto right = upper_bound(nums.begin(),nums.end(),target);
if(left == right) return {-1,-1};

return {(int)(left-nums.begin()),(int)(right-nums.begin() -1)};
}
};

解释：

代码解析

lower_bound 和 upper_bound 的作用：
- std::lower_bound(nums.begin(), nums.end(), target)：
  - 返回指向数组中第一个 大于或等于 target 的元素的迭代器。
- std::upper_bound(nums.begin(), nums.end(), target)：
  - 返回指向数组中第一个 大于 target 的元素的迭代器。
- 如果目标值不在数组中，lower_bound 和 upper_bound 会返回相同的迭代器指向某个位置，因此可以用它们的比较来判断目标值是否存在。
处理目标值不在数组中的情况：
- 如果 lower_bound 和 upper_bound 的返回值相同，说明目标值在数组中不存在，直接返回 {-1, -1}。

为什么需要减去 nums.begin()

在 STL 中，lower_bound 和 upper_bound 返回的不是数组的索引，而是指向数组元素的迭代器。如果需要将迭代器转换为整数索引，就需要计算该迭代器与起始迭代器 (nums.begin()) 之间的距离。

方法二：

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 初始化结果为 {-1, -1}，表示未找到目标值的起始和结束位置
vector<int> result = {-1, -1};

// 初始化左右指针，l 指向数组的起始位置，r 指向数组的末尾位置
int l = 0, r = nums.size() - 1;

// 开始二分查找，循环条件是左指针小于等于右指针
while (l <= r) {
// 计算中间位置，防止整型溢出
int mid = l + (r - l) / 2;

// 如果中间值小于目标值，说明目标值在右半部分，移动左指针
if (nums[mid] < target)
l = mid + 1;

// 如果中间值大于目标值，说明目标值在左半部分，移动右指针
else if (nums[mid] > target)
r = mid - 1;

// 如果左边界的值小于目标值，尝试向右收缩左边界
else if (nums[l] < target)
l++;

// 如果右边界的值大于目标值，尝试向左收缩右边界
else if (nums[r] > target)
r--;

// 如果当前左右指针的值都等于目标值，找到范围
else {
result[0] = l; // 起始位置为左指针的位置
result[1] = r; // 结束位置为右指针的位置
return result; // 直接返回结果
}
}

// 如果循环结束仍未找到目标值，返回初始的 {-1, -1}
return result;
}
};

3. 240. 搜索二维矩阵 II

中等

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

方法一：

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size(); // 矩阵的行数
int cols = matrix[0].size(); // 矩阵的列数

// 起始点：右上角
int rowIndex = 0, colIndex = cols - 1;
while (rowIndex < rows && colIndex >= 0) {
if (target > matrix[rowIndex][colIndex])
rowIndex++; // 目标值更大，向下移动
else if (target < matrix[rowIndex][colIndex])
colIndex--; // 目标值更小，向左移动
else
return true; // 找到目标值
}
return false; // 未找到目标值
}
};

方法二：

// 二分查找
class Solution {
public:
// 函数声明，用于在矩阵中搜索目标值
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 获取矩阵的行数和列数
int m = matrix.size(), n = matrix[0].size();

// 遍历每一行
for(int i{}; i < m; ++i) {
// 在当前行中使用lower_bound函数查找第一个不小于target的元素
// lower_bound是STL中的算法，用于在已排序的序列中查找第一个不小于给定值的元素
auto iter = lower_bound(matrix[i].begin(), matrix[i].end(), target);

// 如果找到了且该元素等于目标值，则返回true
if(iter != matrix[i].end() && *iter == target) return true;
}
// 如果遍历完所有行都没有找到目标值，则返回false
return false;
}
};

3. 287. 寻找重复数

中等

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size(); // 获取数组的长度
int slow = 0, fast = 0; // 初始化两个指针，slow和fast，都指向数组的起始位置

// 第一个循环：使用快慢指针找到相遇点，即环的某个节点
do {
slow = nums[slow]; // 慢指针向前移动一步
fast = nums[nums[fast]]; // 快指针向前移动两步
} while (slow != fast); // 如果两个指针相遇，则跳出循环

// 重置慢指针到数组的起始位置
slow = 0;
// 第二个循环：再次使用快慢指针找到环的入口，即重复的元素
while (slow != fast) {
slow = nums[slow]; // 两个指针都从相遇点和起始位置向前移动一步
fast = nums[fast];
}

// 返回找到的重复元素的值
return slow;
}
};

解释：

初始化：
- slow 和 fast 都从索引 0 开始。
- nums = [1,3,4,2,2]
第一次循环：
- slow = nums[0] = 1（索引 0 指向 1）
- fast = nums[nums[0]] = nums[1] = 3（索引 1 指向 3）
- slow = nums[1] = 3（索引 1 指向 3）
- fast = nums[nums[1]] = nums[3] = 2（索引 3 指向 2）
- slow = nums[3] = 2（索引 3 指向 2）
- fast = nums[nums[3]] = nums[2] = 4（索引 2 指向 4）
- slow = nums[2] = 4（索引 2 指向 4）
- fast = nums[nums[2]] = nums[4] = 2（索引 4 指向 2）
- 现在 slow 和 fast 在索引 2 相遇。
重置 slow：
- 将 slow 重置到索引 0。
第二次循环：
- slow = nums[0] = 1（索引 0 指向 1）
- fast = nums[2] = 4（索引 2 指向 4）
- slow = nums[1] = 3（索引 1 指向 3）
- fast = nums[4] = 2（索引 4 指向 2）
- slow = nums[3] = 2（索引 3 指向 2）
- 现在 slow 和 fast 在索引 2 相遇。

由于 slow 和 fast 在索引 2 相遇，数组中的重复元素是 nums[2] = 2。因此，输出是 2。

4. 35. 搜索插入位置

简单

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

请必须使用时间复杂度为 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

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0; // 初始化左指针为数组的开始
int n = nums.size(); // 获取数组的长度
int right = n - 1; // 初始化右指针为数组的末尾
while (left <= right) { // 当左指针不大于右指针时，继续循环
int middle = (left + right) / 2; // 计算中间位置的索引
if (nums[middle] < target) { // 如果中间元素小于目标值
left = middle + 1; // 调整左指针到中间位置的右侧
} else if (nums[middle] > target) { // 如果中间元素大于目标值
right = middle - 1; // 调整右指针到中间位置的左侧
} else { // 如果中间元素等于目标值
return middle; // 返回中间位置的索引，因为找到了目标值
}
}

// 如果循环结束，说明目标值不在数组中，返回right + 1作为插入位置
return right + 1;
}
};