二分查找思想概述
二分查找（Binary Search）是算法中最基础的 O(log n) 查找技术，适用于 有序数组（或部分有序）中的查找、最值、边界定位等场景。其核心思想是 不断缩小搜索区间，通过比较中间元素与目标值的关系，排除一半区间。
虽然二分查找代码简短，但 边界条件（left < right vs left <= right） 和 区间收缩（left = mid + 1 vs left = mid） 极易出错。掌握一套稳定的模板至关重要：
// 基础模板：查找目标值（无重复）
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
LeetCode 热门 100 题中有六道二分经典题，覆盖了 标准二分、边界查找、旋转数组、二维矩阵、双数组 等多种变体。下面逐一拆解。
1. 搜索插入位置（LeetCode 35）
题目：给定排序数组和目标值，若找到则返回下标，若未找到则返回它应该插入的位置（保持有序）。
核心思路：标准二分，当 nums[mid] < target 时 left = mid + 1，否则 right = mid - 1。最终返回 left，它即为插入位置。
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
复杂度：时间 O(log n)，空间 O(1)。
关键点：left 最终停在第一个大于等于 target 的位置，即插入位置；循环条件 <= 确保能处理所有情况。
2. 搜索二维矩阵（LeetCode 74）
题目：矩阵每行升序，且每行的第一个元素大于上一行的最后一个元素（即整体有序），判断目标是否存在。
核心思路：将二维矩阵视作一维有序数组，长度为 m * n，用标准二分，通过 mid / n 和 mid % n 映射到行列。
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = matrix[mid / n][mid % n];
if (val == target) return true;
else if (val < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
复杂度：时间 O(log(mn))，空间 O(1)。
关键点：一维索引到二维坐标的映射是核心；此题也可用两次二分（先找行再找列），但一维映射更简洁。
3. 在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）
题目：给定升序数组（可含重复元素），求目标值的起始和结束下标，不存在则返回 [-1, -1]。
核心思路：分别查找左边界（第一个 >= target）和右边界（最后一个 <= target）。可用两次二分，或封装一个函数 binarySearch(nums, target, isLeft) 控制收缩方向。
public int[] searchRange(int[] nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && nums[leftIdx] == target) {
return new int[]{leftIdx, rightIdx};
}
return new int[]{-1, -1};
}
private int binarySearch(int[] nums, int target, boolean isLeft) {
int left = 0, right = nums.length - 1;
int idx = nums.length; // 默认为长度（表示不存在）
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target || (isLeft && nums[mid] >= target)) {
right = mid - 1;
idx = mid;
} else {
left = mid + 1;
}
}
return idx;
}
复杂度：时间 O(log n)，空间 O(1)。
关键点：左边界查找时，当 nums[mid] >= target 时收缩右边界，记录 mid；右边界查找可复用同一逻辑，只需返回 idx-1，或修改条件为 > 与 >= 的区分。
4. 搜索旋转排序数组（LeetCode 33）
题目：升序数组在某个下标处旋转（如 [0,1,2,4,5,6,7] 变为 [4,5,6,7,0,1,2]），判断目标是否存在。
核心思路：每次取 mid，根据 nums[left] 与 nums[mid] 的关系判断哪一侧是有序的。若目标值在有序区间内，则在该区间继续二分；否则在另一侧。
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 左半部分有序
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // 右半部分有序
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
复杂度：时间 O(log n)，空间 O(1)。
关键点：判断有序区间时使用 <=（处理重复元素时可扩展，但本题无重复）；通过比较目标是否在有序区间内决定移动方向。
5. 寻找旋转排序数组中的最小值（LeetCode 153）
题目：旋转升序数组（无重复），找出最小值。
核心思路：利用性质，最小值是唯一满足 nums[mid] > nums[right] 时在右半部分，否则在左半部分（包括 mid）。
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
复杂度：时间 O(log n)，空间 O(1)。
关键点：循环条件为 left < right，最终 left 指向最小值；比较对象是 nums[mid] 与 nums[right]，而不是 nums[left]，这样更稳定。
6. 寻找两个正序数组的中位数（LeetCode 4）
题目：给定两个升序数组，求它们合并后的中位数（O(log(m+n))）。
核心思路：在较短的数组上进行二分，确定两个数组的分割线，使得左右两侧元素个数相等（或差一），且左侧最大值 <= 右侧最小值。通过调整分割位置，直至满足条件。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int left = 0, right = m;
while (left <= right) {
int i = left + (right - left) / 2;
int j = (m + n + 1) / 2 - i;
int left1 = (i == 0) ? Integer.MIN_VALUE : nums1[i-1];
int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int left2 = (j == 0) ? Integer.MIN_VALUE : nums2[j-1];
int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (left1 <= right2 && left2 <= right1) {
if ((m + n) % 2 == 0) {
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
} else {
return Math.max(left1, left2);
}
} else if (left1 > right2) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0.0;
}
复杂度：时间 O(log(min(m,n)))，空间 O(1)。
关键点：将问题转化为"在两个有序数组中寻找一个分割点，使左右两侧元素总数平衡"；通过二分较短的数组，计算另一数组的分割位置；边界处理使用 MIN_VALUE 和 MAX_VALUE 简化判断。
六题对比与总结
| 题目 | 核心变体 | 循环条件 | 更新策略 | 特殊技巧 |
|---|---|---|---|---|
| 搜索插入位置 | 标准二分 | <= |
left = mid+1, right = mid-1 |
返回 left |
| 搜索二维矩阵 | 整体有序 | <= |
同上 | 一维映射二维 |
| 查找首末位置 | 边界查找 | <= |
收缩方向控制 | 左右边界分离 |
| 搜索旋转数组 | 部分有序 | <= |
判断有序区间 | 分段确定目标位置 |
| 寻找最小值 | 旋转最小值 | < |
left = mid+1 / right = mid |
比较 nums[mid] 与 nums[right] |
| 两数组的中位数 | 双数组分割 | <= |
二分较短数组 | 边界值 + 奇偶判断 |
共同本质：二分查找的核心在于 “通过比较，排除不可能区间”。无论是旋转数组还是双数组，只要能将问题转化为"满足某个条件的元素位置"，二分就能派上用场。
总结心法：
- 确定搜索空间（数组下标区间）和循环条件（
<=或<）。 - 确定比较对象（与 target 或与边界值）。
- 确定收缩规则（何时
left = mid+1，何时right = mid-1）。 - 处理边界特殊情况（无重复、存在重复、是否越界）。