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[r]当参照。- 如果
nums[mid] > nums[r]，说明 mid 还在左侧那段大数区，最小值一定在右边。 - 否则 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
最优解（二分切分：在较短数组上找“完美分割”）
最优解讲解（通俗版 + 推理过程）
- 目标：不把两个数组合并（合并要 (O(m+n))），而是用 (O(\log \min(m,n))) 找中位数。
- 关键想法：把“中位数”改写成“把所有数分成左右两半”：
- 左半部分包含总数的一半（向下取整），右半部分包含剩下的。
- 中位数只和“左半最大值”“右半最小值”有关。
- 我们要找到一种切分：在 nums1 里切一刀取 i 个到左边，在 nums2 里取 j 个到左边，使得：
- 左边元素总数 =
totalLeft - 且左边最大 ≤ 右边最小（两数组各自有序后，这个条件可用四个边界值判断）
- 左边元素总数 =
- 完美分割条件为什么是这两个不等式？
- 左边最大可能来自
aLeft或bLeft - 右边最小可能来自
aRight或bRight - 只要
aLeft <= bRight且bLeft <= aRight，就保证“所有左边都 ≤ 所有右边”。
- 左边最大可能来自
- 为什么在短数组上二分？
- i 的范围是
[0..m]，m 越小二分越快，而且 j 会自动由totalLeft - i决定。
- i 的范围是
- 找到完美分割后怎么取答案？
- 总长度奇数：中位数就是左半最大值
max(aLeft,bLeft) - 总长度偶数：中位数是
(左半最大 + 右半最小)/2
- 总长度奇数：中位数就是左半最大值
类似题目（二分切分：用四个边界判断是否“分割正确”）
choose i in A, j in Bif A[i-1] <= B[j] && B[j-1] <= A[i]: okelse adjust i by binary search