常见算法-二分查找

写在前面

二分查找应该是我刷LeetCode时最早接触的算法之一，当时觉得挺简单的——不就是折半查找嘛。结果真正写起来才发现，left、right、mid这些边界条件一不小心就写错，要么死循环，要么漏掉元素。后来才意识到，二分查找看似简单，其实细节很多。

这篇文章我会按照自己的理解，把二分查找从基础到变种都梳理一遍。

二分查找是什么

最基础的二分查找就是在有序数组中找一个目标值，每次通过比较中间元素，排除一半的搜索空间。

举个例子，在 [1, 3, 5, 7, 9, 11, 13] 中找 7：

1	第1次: 范围 [1,3,5,7,9,11,13]，中间是 7，找到了！

如果找 8 呢：

1
2
3

第1次: 范围 [1,3,5,7,9,11,13]，中间是 7，8 > 7，去右边找
第2次: 范围 [9,11,13]，中间是 11，8 < 11，去左边找
第3次: 范围 [9]，9 != 8，找不到

简单来说就是：每次排除一半，直到找到或者范围为空。

时间复杂度 O(log n)，这也是二分查找的魅力所在——数据量越大，优势越明显。100万条数据，最多查20次。

基础模板

我自己用的最多的是左闭右闭区间的写法，也就是 [left, right]。

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;  // 注意是 n-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;  // 没找到
}

几个细节

为什么是 right = nums.size() - 1？
因为我们用的是闭区间 [left, right]，右边界要包含最后一个元素。
为什么循环条件是 left <= right？
当 left == right 时，区间 [left, right] 还有一个元素没检查，所以要用 <=。
为什么是 mid = left + (right - left) / 2？
如果写成 (left + right) / 2，当 left 和 right 都很大时可能溢出。虽然LeetCode数据范围一般不会溢出，但这是个好习惯。
为什么是 left = mid + 1 而不是 mid？
因为 nums[mid] 已经检查过了，不是目标值，所以可以排除。

左闭右开写法

有些人喜欢用左闭右开区间 [left, right)，也就是右边界不包含。

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();  // 注意是 n（不包含）
    
    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;  // 注意是 mid，不是 mid - 1
        }
    }
    
    return -1;
}

说实话，我一开始也纠结用哪种写法。后来发现，选一个用熟就行，关键是理解区间的含义，不要混用。

变种1：查找左边界

有时候数组中有重复元素，我们要找第一个等于 target 的位置。

比如 [1, 2, 2, 2, 3] 中找 2 的左边界，应该返回索引 1。

int searchLeft(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;     // 记录位置
            right = mid - 1;  // 继续向左找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

核心思路：找到 target 后不立即返回，而是继续向左缩小范围。

变种2：查找右边界

同理，找最后一个等于 target 的位置。

[1, 2, 2, 2, 3] 中找 2 的右边界，应该返回索引 3。

int searchRight(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;    // 记录位置
            left = mid + 1;  // 继续向右找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

变种3：找第一个大于等于target的位置

这个在实际应用中很常见，比如查找插入位置。

int lowerBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;  // nums[mid] >= target，可能是答案
        }
    }
    
    return left;
}

注意：这里我用的是左闭右开写法 [left, right)，因为这样写起来比较简洁。

如果数组是 [1, 3, 5, 7]，target = 4，返回索引 2（也就是 5 的位置）。

变种4：找第一个大于target的位置

int upperBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] <= target) {  // 注意是 <=
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

实战题目

LeetCode 704 - 二分查找

最基础的题，直接套模板就行。

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 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 35 - 搜索插入位置

给定一个排序数组和目标值，如果找到返回索引，否则返回它应该被插入的位置。

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

其实就是找第一个 >= target 的位置（lower_bound）。

LeetCode 34 - 在排序数组中查找元素的第一个和最后一个位置

这题就是找左右边界的综合应用。

vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.empty()) return {-1, -1};
    
    int left = searchLeft(nums, target);
    if (left == -1) return {-1, -1};  // 没找到
    
    int right = searchRight(nums, target);
    return {left, right};
}

LeetCode 69 - x 的平方根

计算并返回 x 的平方根（只保留整数部分）。

这题其实是在 [0, x] 中找最后一个满足 i * i <= x 的数。

int mySqrt(int x) {
    if (x == 0) return 0;
    
    int left = 1, right = x;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (mid <= x / mid) {  // 避免溢出
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

小技巧：用 mid <= x / mid 代替 mid * mid <= x，避免整数溢出。

LeetCode 33 - 搜索旋转排序数组

这题有点意思，数组被旋转了，比如 [4,5,6,7,0,1,2]。

核心思路：虽然整体无序，但肯定有一半是有序的。先判断哪半边有序，再判断 target 在不在有序的那半边。

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        
        // 左半边有序
        if (nums[left] <= nums[mid]) {
            // target 在左半边
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 右半边有序
        else {
            // target 在右半边
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

LeetCode 153 - 寻找旋转排序数组中的最小值

还是旋转数组，这次是找最小值。

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // 右半边无序，最小值在右边
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        }
        // 左半边无序或全部有序，最小值在左边（包括mid）
        else {
            right = mid;
        }
    }
    
    return nums[left];
}

二分答案

除了在数组中二分查找，还有一类题是二分答案。也就是答案有一定范围，通过二分猜答案，然后验证是否可行。

经典例题：LeetCode 875 - 爱吃香蕉的珂珂

珂珂有 N 堆香蕉，第 i 堆有 piles[i] 根香蕉。她可以决定每小时吃香蕉的速度 K（根/小时）。每小时她会选择一堆香蕉，吃 K 根（如果这堆不够 K 根，她会吃完这堆就停下来）。

问：在 H 小时内吃完所有香蕉，最小的 K 是多少？

思路：K 的范围是 [1, max(piles)]，我们可以二分 K 的值。对于每个 K，检查能否在 H 小时内吃完。

int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1;
    int right = *max_element(piles.begin(), piles.end());
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // 检查能否在 h 小时内吃完
        long long hours = 0;
        for (int pile : piles) {
            hours += (pile + mid - 1) / mid;  // 向上取整
        }
        
        if (hours <= h) {
            right = mid;  // 可以吃完，尝试更小的速度
        } else {
            left = mid + 1;  // 吃不完，需要更快的速度
        }
    }
    
    return left;
}

小技巧：(pile + mid - 1) / mid 是向上取整的技巧，等价于 ceil(pile / mid)。

容易踩的坑

循环条件写错
left <= right 还是 left < right？取决于区间定义。记住：闭区间用 <=，半开区间用 <。
边界更新写错
left = mid 还是 left = mid + 1？记住：已经检查过 mid 了，要排除就用 +1 或 -1。
死循环
如果边界更新不当，可能导致 left 和 right 永远无法相遇。比如用 left < right 但更新时用 right = mid，当 left = mid - 1 时就会死循环。
溢出问题
写成 (left + right) / 2 在理论上可能溢出，虽然LeetCode一般不会卡这个。
边界条件遗漏
数组为空、target 不在范围内等特殊情况要单独处理。

总结

二分查找虽然看起来简单，但要写对还是需要细心。我的建议是：

选定一种写法（闭区间或半开区间），熟练掌握它
理解区间不变量：每次循环后，答案一定在 [left, right] 区间内
多刷题：变种题做多了，自然就有感觉了

常见的二分查找题型：

基础二分：LeetCode 704
查找边界：LeetCode 34
旋转数组：LeetCode 33, 153
二分答案：LeetCode 875, 1011, 410