二分查找
@[toc]
| 题目 | 备注 |
| ------------------------------------------------------------ | ---------------------------- |
| [153.寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/)（补充题） | 查找左边界 |
| [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array) | 查找左边界+标准二分 |
| [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/) | 查找左边界+查找右边界 |
| [240. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii) | 从右上角出发开始遍历 |
| [4. 寻找两个正序数组的中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays) | 不好理解，可选择性放弃 |
| [287. 寻找重复数](https://leetcode-cn.com/problems/find-the-duplicate-number) | 收缩的不是下标，而是具体数值 |
## 153.寻找旋转排序数组中的最小值
**题目**：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
**思路**：
题目中所说的旋转次数啥的不要在意，其实目的就是告诉你这个数组是部分有序的，并且题目还指明了不存在重复元素，这不就正好对应了二分查找边界的第一种情况~
不过这个题目有一点需要考虑的是，就是它没有 target，没有 target 我怎么去进行比较？
这样我们人为地去设定一个 target：
- 我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
**示例**：
以示例 `nums = [4,5,6,7,0,1,2]` 为例：
初始状态
- 范围：`left = 0`，`right = 6`，`mid = 3`（值为 `7`）。
- 比较：`nums[mid] = 7` > `nums[right] = 2` ➔ 最小值在右半部分，更新 `left = mid + 1 = 4`。
第二次循环
- 范围：`left = 4`，`right = 6`，`mid = 5`（值为 `1`）。
- 比较：`nums[mid] = 1` ≤ `nums[right] = 2` ➔ 最小值在左半部分或 `mid` 处，更新 `right = mid = 5`。
第三次循环
- 范围：`left = 4`，`right = 5`，`mid = 4`（值为 `0`）。
- 比较：`nums[mid] = 0` ≤ `nums[right] = 1` ➔ 更新 `right = mid = 4`。
终止条件
- `left == right`，循环结束，返回 `nums[left] = 0`。
**题解**：
```java
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int target = nums[right];
int mid = left + ((right - left) >> 1);
// 收缩左边界
if (nums[mid] > target) {
// 说明 mid 在最小值的左边（最小值在 mid 的右边）
left = mid + 1;
} else {
// 收缩右边界（说明 mid 在最小值的右边，最小值在 mid 的左边）
right = mid;
}
}
return nums[left];
}
}
```
## 33.搜索旋转排序数组
**题目**：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
**思路**：
先找最小值，把一个部分有序的数组分成两个有序的子数组，然后在这俩子数组中做二分查找。注意特殊 case：最小值等于 taget、最小值是 nums[0]
**题解**：
```java
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
// 找到旋转数组中的最小值
int index = findMin(nums);
// 特殊情况：如果最小值 == target，直接返回
if (nums[index] == target) {
return index;
}
// 特殊情况：如果最小值的下标为 0，表示 nums 全局有序，在 nums[0, nums.length - 1] 上做标准二分查找
if (index == 0) {
return find(nums, target, 0, nums.length - 1);
}
// target 在前半部分的有序子数组中
if (target >= nums[0] && target <= nums[index - 1]) {
return find(nums, target, 0, index - 1);
}
// target 在后半部分的有序子数组中
return find(nums, target, index + 1, nums.length - 1);
}
// 找到 nums 旋转数组中的最小值
private int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > nums[right]) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
// nums[left, right] 中查找 target
private int find(int[] nums, int target, int left, int right) {
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
}
```
## 34.在排序数组中查找元素的第一个和最后一个位置
**题目**：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
**思路**：
查左边界 + 查右边界，所谓查左边界的意思就是，即使 nums[right] == target 了，还要继续往左查直到 target 首次出现（相当于不断收缩右指针）
需要注意左右边界 mid 取值问题，left + (right - left) / 2 偏左，left + (right - left) / 2 + 1偏右
具体步骤如下：
1. 左边界查找：
- 使用二分查找，找到第一个等于 `target` 的元素。
- 若中间元素 `< target`，左边界向右收缩；否则右边界向左收缩（即使相等也要向左收缩，这样才能找到左边界）。
- 最终检查左边界是否有效。
2. 右边界查找：
- 在左边界有效的前提下，再次使用二分查找。
- 中间元素计算时向右取整，避免死循环。
- 若中间元素 `> target`，右边界向左收缩；否则左边界向右收缩（即使相等也要向右收缩，这样才能找到右边界）。
3. 提前终止优化：
- 若左边界未找到，直接返回 `[-1, -1]`，避免无效的右边界查找。
**题解**：
```java
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if (nums == null || nums.length == 0) return res;
// 查找左边界
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[left] != target) return res; // 提前终止
res[0] = left;
// 查找右边界
right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2 + 1; // 向右取整
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
res[1] = right;
return res;
}
}
```
## 240.搜索二维矩阵 II
**题目**：https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
**思路**：
数组从左到右和从上到下都是升序的，如果从右上角出发开始遍历呢？
会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。
所以我们可以把 target 和当前值比较：
- 如果 target 的值大于当前值，那么就向下走
- 如果 target 的值小于当前值，那么就向左走
- 如果相等的话，直接返回 true
也可以换个角度思考
如果 target 的值小于当前值，也就意味着当前值所在的列肯定不会存在 target 了，可以把当前列去掉，从新的右上角的值开始遍历。
同理，如果 target 的值大于当前值，也就意味着当前值所在的行肯定不会存在 target 了，可以把当前行去掉，从新的右上角的值开始遍历。
总结：每行做二分就可以，但是只用到了行有序，没有用到列有序。可以考虑从右上角开始遍历，往左就是变小，往下就是变大，类似于二叉搜索树
**题解**：
```java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int x = 0;
int y = matrix[0].length - 1;
while (x <= matrix.length - 1 && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
else if (matrix[x][y] > target) {
y --;
}
else {
x ++;
}
}
return false;
}
}
```
## 4.寻找两个正序数组的中位数
**题目**：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
**思路**：
核心思路是将其转为求两个正序数组中第 k 大的数。可以直接看官方题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
- 要找到有序数组 nums1 和 nums2 的第 k 小的元素，我们可以比较 nums1[k/2 - 1] 和 nums2[k/2 -1]。nums1[k/2 - 1] 和 nums2[k/2 - 1] 的前面（不包括他们本身）都有 k/2 - 1 个元素
- 对于 nums1[k/2 - 1] 和 nums2[k/2 - 1] 中的最小值，最多会有 (k/2 - 1) + (k/2 - 1) = k - 2 个元素比他小，那么他就肯定不是第 k 小的数了！
**题解**：
```java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
// 奇数, 中位数是第 len/2 + 1 个数
if (len % 2 == 1) {
int k = len / 2 + 1;
return findK(nums1, nums2, k);
}
// 偶数，中位数是第 len/2 和 第 len/2 + 1 个数
int k1 = len / 2;
int k2 = len / 2 + 1;
return (findK(nums1, nums2, k1) + findK(nums1, nums2, k2)) / 2;
}
// 返回 nums1 和 nums2 中第 k 小的数的值
private double findK(int[] nums1, int[] nums2, int k) {
// nums1 的下标
int index1 = 0;
// nums2 d
int index2 = 0;
while (true) {
// nums1 为空，直接 nums2 的第 k 个数就行
if (index1 == nums1.length) {
return nums2[index2 + k - 1];
}
// nums2 为空，直接 nums1 的第 k 个数就行
if (index2 == nums2.length) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
// nums1 和 nums2 分别取 k/2 个数
int half = k / 2;
// nums1[index1, newIndex1]
int newIndex1 = Math.min(index1 + half - 1, nums1.length - 1);
// nums2[index2, newIndex2]
int newIndex2 = Math.min(index2 + half - 1, nums2.length - 1);
if (nums1[newIndex1] <= nums2[newIndex2]) {
// 第 k 小的数肯定不在 [index1, newIndex1]
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
// 第 k 小的数肯定不在 [index2, newIndex2]
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
}
```
## 287.寻找重复数
**题目**：https://leetcode.cn/problems/find-the-duplicate-number/description/
**思路**：
二分查找数值范围
1. 数值范围二分：将数值范围 `[1, n]` 划分为左右两半，统计左半范围内元素出现的次数。
- 若次数超过左半区间的长度，说明重复数在左半部分。
- 否则，重复数在右半部分。
2. 逐步缩小范围：通过不断二分数值范围，最终锁定重复数。
**示例**：
以示例 `nums = [1, 3, 4, 2, 2]`（`n=4`）为例：
步骤 1：初始范围 [1, 4]
- 中间值 `mid = (1+4)/2 = 2`，统计数值在 `[1, 2]` 范围内的元素个数：`1, 2, 2` ➔ 共 3 个。
- 比较：实际个数（3）> 理论个数（2），说明重复数在 `[1, 2]` 区间。
步骤 2：缩小范围至 [1, 2]
- 中间值 `mid = (1+2)/2 = 1`，统计数值在 `[1, 1]` 范围内的元素个数：`1` ➔ 共 1 个。
- 比较：实际个数（1）= 理论个数（1），说明重复数在右半部分 `[2, 2]`。
步骤 3：锁定重复数
- 范围缩小至 `min = 2`, `max = 2`，找到重复数 `2`。
**题解**：
```java
class Solution {
public int findDuplicate(int[] nums) {
int min = 1; // 数值范围左边界
int max = nums.length - 1; // 数值范围右边界（n）
while (min < max) {
int mid = (min + max) / 2;
int cnt = 0;
// 统计数值在 [min, mid] 范围内的元素个数
for (int num : nums) {
if (num >= min && num <= mid) {
cnt++;
}
}
if (cnt > mid - min + 1) {
max = mid; // 重复数在左半部分
} else {
min = mid + 1; // 重复数在右半部分
}
}
return min; // 最终 min == max，即为重复数
}
}
```