vvrf / DSA.log

问题拆解

一个升序数组在未知位置被旋转过（如 [4,5,6,7,0,1,2]），要求在 O(log n) 时间内找到目标值的下标，找不到返回 -1。

线性扫描当然能做但不达标，O(log n) 明示了二分。可标准二分依赖“比中点小就往左、比中点大就往右”的全局有序性，旋转恰好把它破坏了。关键观察是：从任意位置把数组切成两半，断点只会落在其中一半里——另一半必然是完整升序的。而判断哪一半有序只需一次比较：nums[left] <= nums[mid] 则左半有序，否则断点在左半、右半必有序。

二分的本质不是“数组有序”，而是“每轮能用 O(1) 的判断排除一半”。这里的判断分两步：先认出有序的那半，再看 target 在不在它的值域里。

有序的那一半值域清晰（就是两端点的闭区间），可以精确回答“target 在不在里面”：在，就收缩到这一半；不在，就必然在另一半——哪怕另一半长什么样我们并不清楚。

判断有序半边的二分

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 (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // target 落在有序的左半
            } else {
                left = mid + 1;
            }
        } else { // 右半有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // target 落在有序的右半
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:  # 左半有序（注意取等）
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # target 落在有序的左半
            else:
                left = mid + 1
        else:  # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1  # target 落在有序的右半
            else:
                right = mid - 1
    return -1

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        if nums[left] <= nums[mid] { // 左半有序（注意取等）
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1 // target 落在有序的左半
            } else {
                left = mid + 1
            }
        } else { // 右半有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1 // target 落在有序的右半
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

pub fn search(nums: Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right) = (0i32, nums.len() as i32 - 1);
    while left <= right {
        let mid = left + (right - left) / 2;
        let (l, m, r) = (left as usize, mid as usize, right as usize);
        if nums[m] == target {
            return mid;
        }
        if nums[l] <= nums[m] {
            // 左半有序（注意取等）
            if nums[l] <= target && target < nums[m] {
                right = mid - 1; // target 落在有序的左半
            } else {
                left = mid + 1;
            }
        } else {
            // 右半有序
            if nums[m] < target && target <= nums[r] {
                left = mid + 1; // target 落在有序的右半
            } else {
                right = mid - 1;
            }
        }
    }
    -1
}

最阴险的细节是 nums[left] <= nums[mid] 里的等号。当区间只剩两个元素时 mid == left，nums[left] == nums[mid] 必然成立——此时“左半”只有一个元素，单元素当然算有序，应该走左半有序的分支。若写成严格小于，这种情况会被误判为“右半有序”，用错值域判断，比如在 [3,1] 里找 1 就会返回 -1。另一处对称的细节是值域判断的开闭：nums[left] <= target < nums[mid] 左闭右开，因为 nums[mid] 已经在上面和 target 比较过不相等，两端都写闭区间不算错，但明确开闭能帮你想清楚每个元素被谁覆盖。

复杂度

指标	复杂度	原因
时间	`O(log n)`	每轮排除一半，与标准二分相同
空间	`O(1)`	只用两个边界指针

可以迁移的模式

二分的适用条件可以放宽为“存在 O(1) 判据决定去哪一半”，不必全局有序；
处理被旋转/分段的有序结构，先认出“规整的那一半”，用它的确定性反推另一半；
二分的等号（<= 还是 <）用最小区间（两个元素）代入检验，这是揪出边界 bug 最快的办法。

它的两个续作——含重复元素的 81 和找最小值的 153——都建立在“判断哪半有序”这同一根轴上，这一篇想透，那两题就是换皮。