vvrf / DSA.log

问题拆解

在升序数组里找目标值，找到返回下标，找不到返回 -1，要求 O(log n)。

思路本身人人都知道：每次拿中间元素和目标比，砍掉一半。真正让二分写错的从来不是取中点，而是几个边界问题搅在一起——循环条件写 < 还是 <=？更新时用 mid 还是 mid ± 1？这些问题没有孤立的答案，它们全都取决于一件事：你如何定义搜索区间。

先定下区间的含义，剩下的每一行代码都只是保持和这个定义一致。

左闭右闭区间

这里采用左闭右闭区间 [left, right]。这意味着左右端点都可能是答案，因此循环条件必须写成 left <= right——当 left == right 时区间里还剩一个候选，仍要检查。

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[mid] < target) {
            left = mid + 1;
        } 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 - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        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[mid] < target {
            left = mid + 1
        } 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;
        match nums[mid as usize].cmp(&target) {
            std::cmp::Ordering::Equal => return mid,
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => right = mid - 1,
        }
    }

    -1
}

为什么是 mid ± 1？判断完 nums[mid] 后，已经确定它不是答案。新的搜索区间不应该再次包含 mid，所以向右时从 mid + 1 开始，向左时到 mid - 1 结束。这同时保证区间每轮严格缩小，不会死循环。

取中点写成 left + (right - left) // 2 而不是 (left + right) // 2，是为了在整数会溢出的语言里避免 left + right 越界；Python 没有这个问题，但保持这个习惯没有坏处。

检查清单

数组是否有序（二分的前提）；
搜索区间是闭区间还是半开区间；
循环条件是否与区间定义一致；
更新边界后，区间是否确实缩小。

复杂度

指标	复杂度	原因
时间	`O(log n)`	每轮把候选区间砍掉一半
空间	`O(1)`	只用三个下标变量

可以迁移的模式

有序结构上找某个值、找第一个/最后一个满足条件的位置；
更广义地：答案单调（某个条件从 false 翻转为 true）时，可以对答案本身二分；
写任何变体前，先把区间定义和循环不变量说出口，再落笔。

只要区间定义、循环条件、边界更新这三件事前后一致，二分就不需要靠背模板。