🎯 二分查找

在有序或部分有序结构中以 O(log n) 定位目标，边界处理是关键（左闭右闭 vs 左闭右开）。

6 题  ·  简单 ×1  中等 ×4  困难 ×1

核心思路

• 搜索插入位置：标准 lower_bound，返回第一个 ≥ target 的位置。
• 搜索二维矩阵：将矩阵展开为一维（mid / n 行，mid % n 列）做标准二分。
• 查找第一个和最后一个位置：两次二分分别求左边界和右边界。
• 搜索旋转排序数组：每次判断左半段或右半段是否有序，再确定 target 在哪侧收缩。
• 旋转数组最小值：与右端点比较：nums[mid] > nums[right] 则最小值在右半，否则在左半（含 mid）。
• 两个正序数组的中位数：在较短数组上二分划分点，保证两侧元素各占一半，O(log(min(m,n)))。