二分查找【各种题型+对应LeetCode习题练习】

目录

什么是二分查找？
标准查找
        LeetCode 704 二分查找
搜索插入位置
        LeetCode 35 搜索插入位置
查找左右边界
        LeetCode 34 查找元素的第一个和最后一个位置
条件最大/最小值
        LeetCode 69 x 的平方根
旋转数组中的搜索
        LeetCode 33 搜索旋转排序数组

什么是二分查找？

二分查找是一种在有序集合中查找目标值的算法，核心思想是：
每次把区间一分为二，逐步缩小查找范围。

基本前提
必须是有序数组 / 区间
具有单调性（递增、递减、先增后减、先减后增等）

常见题型分类

标准查找

题型：在一个有序数组中查找某个目标值 target，如果存在就返回它的下标，否则返回 -1。

标准查找这类题型通常用左闭右闭

LeetCode 704 二分查找

思路：
1. 前提条件分析：
数组是升序排列，满足整体单调性
可以使用二分查找 
2. 目标是什么？
在数组中查找等于 target 的元素
找到就返回下标；找不到就返回 -1
3. 如何判断？
看 nums[mid] 和 target 的大小关系：
相等 → 找到了，返回 mid
小于 target → 目标在右边，left = mid + 1
大于 target → 目标在左边，right = mid - 1
4. 终止条件？
区间为 [left, right]，当 left > right 时，表示整个数组都查过，未命中，返回 -1
上面的思路就是左闭右闭的思路，一会还会展示左闭右开的代码

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;  // 区间 [left, right]
    
    while (left <= right) {  // 这里是 <=，因为 right 是有效下标
        int mid = left + (right - left) / 2;  
        
        if (nums[mid] == target) {
            return mid;  // 找到直接返回下标
        } else if (nums[mid] < target) {
            left = mid + 1;  // target 在右半区间
        } else {
            right = mid - 1;  // target 在左半区间
        }
    }

    return -1;  // 没找到
}

nums = [-1, 0, 3, 5, 9, 12]
target = 9 

int mid = left + (right - left) / 2写成 int mid = (left + right) / 2 不可以吗？

答：可以，但是写成 left + (right - left) / 2 是为了防止整数溢出。
来看两个例子
(left + right) / 2
= (1 + 2147483647) / 2
= 2147483648 / 2  
结果是溢出，mid 变成了负数或者错误值，程序行为不可预测。
因为INT_MAX 的值是2147483647

int mid = left + (right - left) / 2;
// = 1 + (2147483647 - 1) / 2
// = 1 + 1073741823 = 1073741824 
 

左闭右开写法

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();  // 区间 [left, nums.size())

    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 - 1
    }

    return -1;  
}

nums = [-1, 0, 3, 5, 9, 12]
target = 9 

 和左闭右闭的对比

搜索插入位置

题型：在一个升序数组中，查找第一个大于等于 target 的位置；如果数组中存在 target，返回其下标；如果不存在，返回它应插入的位置（保持有序）。

搜索插入位置这类题型通常用左闭右开
该类型题目查找的是满足某个条件的最小下标，这是典型的左边界问题

LeetCode 35 搜索插入位置

思路：
1. 前提条件分析：
数组是升序排列，满足整体单调性
可以使用二分查找来快速定位插入位置
2. 目标是什么？
在数组中查找第一个大于等于 target 的元素的位置；
如果 target 存在，返回它的下标；
如果不存在，返回它应该插入的位置（保持数组有序）
3. 如何判断？
每轮计算中间位置 mid，观察 nums[mid] 与 target 的关系：
nums[mid] >= target
→ 说明目标在 左边或 mid 处，右边界收缩：right = mid
nums[mid] < target
→ 说明目标一定在 右边，左边界收缩：left = mid + 1
4. 终止条件？
区间为 [left, right)，当 left == right 时，区间为空，退出循环；
此时 left 就是第一个满足 nums[i] >= target 的位置；
如果 target 已存在，那就是它的下标；否则就是它该插入的位置。

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) {
            right = mid;  
        } else {
            left = mid + 1; 
        }
    }

    return left;  
}

 nums = [1, 3, 5, 6]
target = 2

最终 left == right == 1，返回下标 1，即 2 应该插入在 3 前面。

查找左右边界

题型：在一个有序数组中查找目标值 target 的第一个出现位置和最后一个出现位置。如果目标不存在，返回 [-1, -1]。

这类题的关键在于：
左边界： 找到第一个 nums[i] == target 的下标
右边界： 找到最后一个 nums[i] == target 的下标

查找左右边界这类题型通常用左闭右开

查找左右边界不是简单地判断 == target 就返回，而是要逼近极限值，
左边界逼向最左，右边界逼向最右。写法与普通二分的核心不同。

LeetCode 34 查找元素的第一个和最后一个位置

思路：
1. 前提条件分析：
数组是非递减排序，整体满足单调性
可以使用二分查找 
2. 目标是什么？
找到 target 在数组中 第一个出现的位置（左边界）
再找出 target 在数组中 最后一个出现的位置（右边界）
3. 如何判断？
左边界查找：
查找第一个满足 nums[mid] >= target 的位置
继续往左收缩，不能提前返回
右边界查找：
查找第一个满足 nums[mid] > target 的位置，然后返回 mid - 1
逻辑等效于 upper_bound(nums.begin(), nums.end(), target) - 1
4. 终止条件？
区间使用左闭右开 [left, right)，终止条件是 left == right
循环结束后 left 是查找到的边界（或插入点），要额外检查是否命中

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

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

vector<int> searchRange(vector<int>& nums, int target) {
    int left = findLeft(nums, target);
    int right = findRight(nums, target);
    if (left <= right && left < nums.size() && nums[left] == target && nums[right] == target) {
        return {left, right};
    }
    return {-1, -1};
}

nums = [5,7,7,8,8,10], target = 8

查找左边界过程（findLeft）

left == 3，结束，左边界是 3

查找右边界过程（findRight）

left = 5，right = 5 → 右边界是 left - 1 = 4

为什么写if (left <= right && left < nums.size() && nums[left] == target && nums[right] == target)？

① left <= right 目的是确保最终区间合法，即右边界不是比左边界小。
如果 target 不存在，findLeft 和 findRight 会出现 left > right。

② left < nums.size() 是目的：防止 left 越界。
因为 findLeft 返回的是第一个 >= target 的位置，可能是 nums.size()（越界）。
比如 target = 20，nums = [1,2,3]，findLeft → 3，而 nums[3] 越界。

③ nums[left] == target && nums[right] == target 目的是确保找到的确实是目标值的边界（避免虚假命中）。
比如target = 4，nums = [1,2,3]，此时：
findLeft → 3
findRight → 2
此时 left > right，且 nums[left/right] 都不等于 target。
④ 为什么没有 right < nums.size() ？
因为 findRight() 的最终返回是 left - 1，所以它永远不会等于 nums.size()。

条件最大/最小值

题型：在某个范围内查找一个满足某种单调条件的最大值或最小值，并不一定是查找某个具体等于 target 的数，而是满足 check 条件的最优边界值。

查找左右边界这类题型通常用左闭右闭

LeetCode 69 x 的平方根​​​​​​​

思路：
这道题要求实现一个求平方根的函数，并且只返回整数部分（也就是舍去小数部分）。可以使用二分查找来高效解决这个问题，因为平方根函数是一个单调递增的函数。随着 x 增加，sqrt(x) 也递增。

1. 前提条件分析：
给定 x 是非负整数，且 x 的范围为 [0, 2^31-1]（题目给出的整数范围）
要求计算平方根并返回整数部分，可以利用二分查找来减少时间复杂度。
为什么二分查找？
由于平方根函数是单调递增的，对于 x 从小到大，sqrt(x) 也是递增的。
这样就可以在一个区间内通过二分查找来找到最大 r，使得 r*r <= x。
2. 目标是什么？
目标是找到最大的整数 r，使得 r * r <= x，即 r 是 x 的平方根的整数部分。
3. 如何判断？
我们需要一个 check 函数 来判断某个 mid 值的平方是否小于或等于 x：
如果 mid * mid <= x，说明 mid 可以作为解，并且我们需要继续向右寻找更大的 mid，直到找到最大的 mid。
否则，如果 mid * mid > x，说明 mid 太大，需要收缩右边界。
4. 终止条件？
区间为 [left, right]，当 left > right 时，停止二分查找。
最终返回的是 right，因为 right 是最后一个满足条件的最大值。

int mySqrt(int x) {
    if (x == 0) return 0;  

    int left = 1, right = x;

    while (left <= right) {  
        int mid = left + (right - left) / 2;
        long long square = 1LL * mid * mid;  

        if (square == x) {
            return mid;  // 找到精确的平方根
        } else if (square < x) {
            left = mid + 1;  // mid 太小，往右继续找
        } else {
            right = mid - 1;  // mid 太大，往左收缩
        }
    }

    return right;  
}

x = 8, left = 1, right = 8

自定义check函数的代码如下

bool check(int mid, int x) {
    return 1LL * mid * mid <= x;  
}

int mySqrt(int x) {
    if (x == 0) return 0;  

    int left = 1, right = x;

    while (left <= right) {  
        int mid = left + (right - left) / 2;

        if (check(mid, x)) {  
            left = mid + 1; 
        } else {
            right = mid - 1; 
        }
    }

    return right; 
}

旋转数组中的搜索

题型：给定一个升序排列的数组，经过旋转后，需要在这个旋转数组中查找一个目标值 target。数组中的元素可能会重复，目标值可能存在也可能不存在。如果找到目标值，返回它的下标；否则返回 -1。

旋转数组中的搜索这类题型通常用左闭右闭 

为什么不能直接使用标准二分查找？
        标准二分查找适用于完全有序的数组，而旋转数组在旋转后，整体数组并不是单调递增或递减，只是被分成了两部分：两部分中各自是有序的。

LeetCode 33 搜索旋转排序数组​​​​​​​

思路：
1. 判断哪一部分是有序的：
可以通过比较 nums[mid] 和 nums[left] 来判断哪一部分是有序的。
如果 nums[mid] >= nums[left]，说明左半部分是有序的。
如果 nums[mid] < nums[left]，说明右半部分是有序的。
2. 根据有序部分调整搜索范围：
如果左半部分是有序的：
如果目标值 target 在左半部分的范围内，即 nums[left] <= target < nums[mid]，则目标值必定在左边，收缩右边界：right = mid - 1。
否则，目标值在右半部分，收缩左边界：left = mid + 1。
如果右半部分是有序的：
如果目标值 target 在右半部分的范围内，即 nums[mid] < target <= nums[right]，则目标值必定在右边，收缩左边界：left = mid + 1。
否则，目标值在左半部分，收缩右边界：right = mid - 1。
3. 终止条件：
当 left > right 时，说明搜索区间已空，目标值不存在，返回 -1。

如果 nums[mid] >= nums[left]，说明左半部分是有序的。
如果 nums[mid] < nums[left]，说明右半部分是有序的。

为什么左半部分有序？
假设没有旋转过，数组的结构本来是递增的，nums[mid]一定大于 nums[left]

即使旋转后，left 到 mid 这一段，仍然是有序的，这部分没有被旋转。

如果是这样，nums[left] <= target < nums[mid] 时，目标值一定在这一段。

为什么右半部分有序？

旋转后的数组中，mid 处的数值小于 left 处的数值，这表明数组的右边（mid 到 right）没有被旋转。这一部分仍然保持递增关系，和原数组一样是有序的。

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

    return -1;  
}

尚未完结