langShift二分查找（题单顺序）
热题 100 - 二分查找分组（按题单顺序）：35 / 74 / 34 / 33 / 153 / 4
本页包含题单「二分查找」分组的全部题目，顺序与 list.json 保持一致。
二分查找统一“防坑提醒”（点击展开）
- 先选定区间语义：
[l, r)（右开）或[l, r]（双闭），一旦选定就不要混用。 - 写清楚不变量：例如 lower_bound 的不变量通常是「答案始终在
[l, r)内」。 - 更新规则要对应语义：右开区间常见写法是
while (l < r)，命中条件时r = mid，否则l = mid + 1。 - 边界用例一定要过：空数组、单元素、全相等、目标在两端、目标不存在。
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] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
最优解（二分找 lower_bound：第一个 >= target 的位置）
最优解讲解（通俗版 + 推理过程）
- 题意翻译：如果 target 在数组里，返回下标；不在的话，返回“插进去还能保持有序”的位置。
- 关键推理：插入位置就是第一个 >= target 的位置（也叫 lower_bound）。
- 如果数组里存在 target，这个位置正好是它第一次出现的位置；
- 如果不存在，落在“刚好比它大的数前面”，插进去仍然有序。
- 为什么用右开区间
[0, n)更舒服？r直接从 n 开始，最后l==r时就是答案；- 不用特殊处理“插到末尾”的情况。
类似题目（二分模板：lower_bound）
let l = 0, r = nwhile (l < r) {mid = (l+r)>>1if (a[mid] >= x) r = midelse l = mid + 1}return l
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
最优解（把矩阵当成一维有序数组做二分）
最优解讲解（通俗版 + 推理过程）
- 题目保证：每行递增，且下一行的第一个 > 上一行最后一个，所以整体是“按行拼起来也递增”。
- 关键推理：把整个矩阵按行展开成一维数组，仍然是升序。
- 如何在一维下标 mid 和二维坐标之间转换？
- 行号：
Math.floor(mid / n) - 列号：
mid % n
- 行号：
- 这样就能直接在区间
[0, m*n-1]上二分。
类似题目（二维 → 一维映射二分）
value(mid) = a[Math.floor(mid / cols)][mid % cols]
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] <= 109nums是一个非递减数组-109 <= target <= 109
最优解（两次二分：lower_bound 与 upper_bound-1）
最优解讲解（通俗版 + 推理过程）
- 目标：找 target 的最左下标和最右下标。
- 关键推理：范围问题可以拆成两个“边界问题”：
- 最左边 = 第一个 >= target（lower_bound）
- 最右边 = 第一个 >= target+1 的位置 - 1（也就是 upper_bound(target)-1）
- 这比“找到一个 target 再往两边扩”更稳，因为扩展最坏会变成 (O(n))。
类似题目（找区间：lb(x) 与 lb(x+1)-1）
L = lowerBound(x)R = lowerBound(x+1) - 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] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
最优解（二分：每次判断哪一半是有序的）
最优解讲解（通俗版 + 推理过程）
- 旋转数组的结构：本来是全有序的，旋转后变成“两个有序段拼起来”，中间有一个断点。
- 二分还能用吗？能，但比较规则要变：
- 在
[l, mid]或[mid, r]里必有一半是有序的（因为只有一个断点）。
- 在
- 推理步骤：
- 先判断左半是否有序：
nums[l] <= nums[mid] - 如果左半有序，再判断 target 是否落在左半区间内；落在就缩右边界，否则去右半。
- 如果左半无序，那么右半必有序，同理判断 target 是否落在右半。
- 先判断左半是否有序：
- 每次都能排除一半区间，保持 (O(\log n))。
类似题目（旋转数组二分模板：先判有序半区再缩边界）
if leftSorted:if target in [l,mid): r=mid-1 else l=mid+1else:if target in (mid,r]: l=mid+1 else r=mid-1
153. 寻找旋转排序数组中的最小值
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.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
最优解（二分：最小值在“无序的一侧”）
最优解讲解（用一个例子，一步一步看二分怎么找到最小值）
🧪 示例数组
nums = [4, 5, 6, 7, 0, 1, 2]
这是一个旋转后的排序数组，原本是 [0, 1, 2, 4, 5, 6, 7]，旋转后最小值 0 跑到了中间。
🔍 第 1 步（第一次二分）
l = 0, r = 6mid = (0 + 6) >> 1 = 3
当前状态：
索引: 0 1 2 3 4 5 6数组: [4, 5, 6, 7, 0, 1, 2]↑mid=3
比较：
nums[mid] = 7nums[r] = 27 > 2 ✔
说明什么？
nums[mid] > nums[r] 意味着：
- mid 还在左侧大数区（4,5,6,7）
- 最小值一定在 mid 的右边（因为右侧有更小的数 2）
🧠 往右找：l = mid + 1 = 4
🔍 第 2 步（继续二分）
l = 4, r = 6mid = (4 + 6) >> 1 = 5
当前状态：
索引: 0 1 2 3 4 5 6数组: [4, 5, 6, 7, 0, 1, 2]↑mid=5
比较：
nums[mid] = 1nums[r] = 21 < 2 ✔
说明什么？
nums[mid] < nums[r] 意味着：
- mid 已经在右侧小数区（0,1,2）
- 最小值在 mid 的左边或就是 mid
🧠 往左找（包含 mid）：r = mid = 5
🔍 第 3 步（继续二分）
l = 4, r = 5mid = (4 + 5) >> 1 = 4
当前状态：
索引: 0 1 2 3 4 5 6数组: [4, 5, 6, 7, 0, 1, 2]↑mid=4
比较：
nums[mid] = 0nums[r] = 10 < 1 ✔
说明什么？
nums[mid] < nums[r]，最小值在左边或就是 mid。
🧠 往左找（包含 mid）：r = mid = 4
🏆 找到最小值！
l = 4, r = 4l === r，退出循环
答案：nums[4] = 0 ✅
📉 二分移动本质
| 情况 | 说明 | 移动方向 |
|---|---|---|
nums[mid] > nums[r] | mid 在左侧大数区 | 👉 往右找 |
nums[mid] < nums[r] | mid 在右侧小数区 | 👈 往左找（包含 mid） |
为什么用 nums[r] 当参照？
因为旋转后，数组被分成两段：
- 左段：大数（比右端点大）
- 右段：小数（比右端点小或等于）
通过比较 mid 和右端点，就能知道 mid 在哪一段，从而知道最小值在哪边。
🧠 关键顿悟点
"我不是在找数，我是在找旋转断点"
旋转断点就是最小值的位置。通过比较 mid 和右端点，每次都能排除一半，这就是二分。
类似题目（找旋转断点：比较 mid 与端点）
if a[mid] > a[r]: l=mid+1 else r=mid
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
最优解（二分切分：在较短数组上找“完美分割”）
最优解讲解（用一个经典例子，一步一步看刀是怎么移动到正确位置的）
🧪 示例数组
A = [1, 3, 8] (短的数组，我们在这里二分)B = [2, 7, 10, 12]
总长度 = 7
左边需要 (7 + 1) // 2 = 4 个数
我们要找：
- 👉 从 A 里拿 i 个
- 👉 从 B 里拿 j = 4 - i 个
🔍 第 1 刀（第一次二分）
A 长度是 3，我们在区间 [0, 3] 里二分
i = 1j = 4 - 1 = 3
切开变成：
A: [1 | 3 8]B: [2 7 10 | 12]
左右两边是：
左边：1, 2, 7, 10右边：3, 8, 12
我们只看边界 4 个数：
| 名字 | 值 |
|---|---|
| Aleft | 1 |
| Aright | 3 |
| Bleft | 10 |
| Bright | 12 |
检查是否满足：
Aleft ≤ Bright → 1 ≤ 12 ✔Bleft ≤ Aright → 10 ≤ 3 ❌
❌ 不满足！
而且是 Bleft > Aright
说明什么？
B 左边最大的 10 比 A 右边最小的 3 还大
👉 说明 A 这边切太少了！
🧠 刀要往 右边移动
🔍 第 2 刀（向右二分）
现在在 A 的区间 [2, 3] 继续二分
i = 2j = 4 - 2 = 2
切开：
A: [1 3 | 8]B: [2 7 | 10 12]
左右两边：
左边：1, 3, 2, 7右边：8, 10, 12
边界值：
| 名字 | 值 |
|---|---|
| Aleft | 3 |
| Aright | 8 |
| Bleft | 7 |
| Bright | 10 |
检查条件：
Aleft ≤ Bright → 3 ≤ 10 ✔Bleft ≤ Aright → 7 ≤ 8 ✔
🎯 完美！
🏆 找到正确切割！
因为总长度是奇数：
中位数 = 左边最大值= max(Aleft, Bleft)= max(3, 7)= 7
📉 二分移动本质
| 情况 | 说明 | 刀移动方向 |
|---|---|---|
Bleft > Aright | A 切太少 | 👉 右移 |
Aleft > Bright | A 切太多 | 👈 左移 |
每次都能排除一半位置，这就是二分。
🧠 关键顿悟点
我们从头到尾：
- ✅ 没合并数组
- ✅ 没真的找"中间位置"
- ✅ 只是不断调整"分界线"
当你脑子里变成：
"我不是在找数，我是在找 平衡分界线"
这题就通了。
💡 算法核心思想
- 目标：不把两个数组合并（合并要 (O(m+n))），而是用 (O(\log \min(m,n))) 找中位数。
- 关键想法：把"中位数"改写成"把所有数分成左右两半"：
- 左半部分包含总数的一半（向下取整），右半部分包含剩下的。
- 中位数只和"左半最大值""右半最小值"有关。
- 为什么在短数组上二分？
- i 的范围是
[0..m]，m 越小二分越快，而且 j 会自动由totalLeft - i决定。
- i 的范围是
类似题目（二分切分：用四个边界判断是否“分割正确”）
choose i in A, j in Bif A[i-1] <= B[j] && B[j-1] <= A[i]: okelse adjust i by binary search