二分查找 图解题解

有序数组里找一个 target，返回什么

给一个升序（从小到大排好）、无重复数字的数组 nums 和目标值 target：在数组里就返回下标，不在返回 -1。题面例子 nums=[-1,0,3,5,9,12]，找 9 返回下标 4，找 2 返回 -1。题目还卡死 O(log n)，不许一个个挨着找。

一个个往后比，为什么撑不到 O(log n)

笨办法是从头扫到尾，一个个和 target 比。数组有 n 个数，最坏（target 排末尾或不存在）要比满 n 次，这就是 O(n)（大 O 记号，衡量数据规模增大时操作量的放大倍数）。n 到百万就得比百万次，O(log n) 把这条路堵死了。

凭什么敢一次丢掉一半数不看

钥匙全在『有序』二字上。看正中间的 nums[mid]（mid 是中点下标）和 target 比：nums[mid] 小于 target，左边只会更小、够不着，左半连 mid 一起扔掉；大于 target 则右半作废。一比砍掉一半，剩下的才是 target 藏身处，这就是二分查找——每次砍掉一半候选的找法。乱序里左右没规律，砍哪半都可能误伤 target。

看中点该往哪半收，闭区间怎么不越界

用两个指针 l、r 圈住没排除的范围，起初 l=0、r=n-1，两端都算数，这叫闭区间 [l,r]。每轮取中点 mid=l+(r-l)//2 和 target 比：相等直接返回 mid；小于 target，l 跳到 mid+1；大于 target，r 退到 mid-1。

这里藏着一条循环不变量（每一轮都成立的保证）：target 若存在，就一定还在 [l,r] 内。收缩必须跨过 mid——比过的 mid 已排除，l 或 r 落到 mid 下一格，范围才真变小。循环条件写 while l<=r，因为 l==r 时闭区间里还剩一格没查。

[-1,0,3,5,9,12] 里找 9、找 2 各几轮

先找 9。l=0、r=5，mid=0+(5-0)//2=2，nums[2]=3 比 9 小，l 跳到 3。第二轮 l=3、r=5，mid=3+(5-3)//2=4，nums[4]=9 相等，返回下标 4，两轮命中。

再找 2。l=0、r=5，mid=2，nums[2]=3 比 2 大，r 退到 1。第二轮 l=0、r=1，mid=0，nums[0]=-1 比 2 小，l 跳到 1。第三轮 l=1、r=1，mid=1，nums[1]=0 比 2 小，l 跳到 2，此时 l 超过 r，范围空了，返回 -1。

缩不动的死循环，卡在 mid 没跨过去

收缩那步最阴：把 l=mid+1 写成 l=mid，比过的 mid 没跨过去，l 卡着不动就成了缩不动的死循环。循环条件也别写成 while l<r，闭区间里 l==r 那一格会被漏掉。mid 写成 (l+r)//2 看着没差，可数组一大 l+r 会超整数上限溢出，得写 l+(r-l)//2 绕开。

复杂度上，每比一次范围减半，n 个数最多 log₂n 次收敛，时间 O(log n)；只用 l、r、mid 三个变量，空间 O(1)。百万个数约 20 次比较，比 O(n) 快几个数量级。

Python

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2   # 防溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1          # 丢左半
        else:
            r = mid - 1          # 丢右半
    return -1

C++

int search(vector<int>& nums, int target){
    int l = 0, r = nums.size() - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;   // 防溢出
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) l = mid + 1;  // 丢左半
        else r = mid - 1;                          // 丢右半
    }
    return -1;
}

Java

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;   // 防溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            l = mid + 1;             // 目标在右半，丢左半
        } else {
            r = mid - 1;             // 目标在左半，丢右半
        }
    }
    return -1;
}