精确与高效：二分查找的完整指南

前言、二分查找算法的概念及思想

二分查找是一种高效的搜索算法，以其简单优雅的实现和出色的性能被广泛应用于计算机科学和工程领域。从理论到实践，这一算法始终是理解数据结构与算法设计的基石。在本文中，我们将深入剖析二分查找的原理、实现和优化，帮助您掌握其核心思想与实际应用。

算法思想

1. 有序性：二分查找要求数组是有序的。
2. 分治思想：将查找范围不断对半缩小，直到找到目标元素或查找范围为空。

步骤

1. 初始化两个指针：左指针 left 指向数组的起始位置，右指针 right 指向数组的末尾。
2. 计算中间位置：mid = left + (right - left) / 2。
3. 比较中间值 array[mid]与目标值 target：
   • 如果相等，返回 mid，表示找到目标元素。
   • 如果目标值小于中间值，将右指针移动到 mid - 1。
   • 如果目标值大于中间值，将左指针移动到 mid + 1。
4. 重复上述步骤，直到左指针大于右指针，表示查找结束，未找到目标值。

时间复杂度和空间复杂度

• 时间复杂度: $O(\log n)$，每次迭代将查找范围减半。
• 空间复杂度: $O(1)$，只需常量级额外空间。

🌶️一、二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/

🫘1. 题目解析

该代码实现的是经典的 二分查找算法，用于查找一个排序数组中的目标值 target，返回目标值的索引。如果目标值存在，返回其索引；如果不存在，返回 -1。

输入:

• 一个有序数组 nums（升序排序）。
• 一个整数 target，表示需要查找的目标值。

输出:

• 如果找到 target，返回其在数组中的索引。
• 如果未找到，返回 -1。

示例:

vector<int> nums = {1, 3, 5, 7, 9, 11};
int target = 7;

返回值为 3，因为 7 在数组中的索引位置是 3。

🫘2. 讲解算法原理

二分查找算法的核心思想是通过不断缩小查找范围来提高效率。给定一个排序数组，二分查找每次将搜索范围减半，逐步逼近目标元素。

具体步骤：

1. 初始化：定义两个指针，left 和 right，分别指向数组的左右边界（初始为 left = 0 和 right = nums.size() - 1）。
2. 迭代过程：
   • 计算中间元素的索引 mid = left + (right - left) / 2。这种方式可以避免 (left + right) 可能导致的整型溢出。
   • 如果 nums[mid] == target，则说明找到了目标值，返回 mid。
   • 如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
   • 如果 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1。
3. 终止条件：当 left > right 时，表示已经搜索完所有可能的范围，仍未找到目标值，因此返回 -1。

🫘3. 编写代码

class Solution {
public:
    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) left = mid + 1;
            else if(nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

🫘4. 总结朴素二分模板

while (left <= right) {  // 循环直到左右边界交错
        int mid = left + (right - left) / 2;  // 防止溢出的中间索引
        if (...)  // 目标值在右半部分
            left = mid + 1;
        else if (...)  // 目标值在左半部分
            right = mid - 1;
        else  // 找到目标值
            return mid;
}

🌶️二、在排序数组中查找元素的第一个和最后一个位置

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

🫘1. 题目解析

题目描述

给定一个非递减排序的整数数组 nums 和一个目标值 target，要求找出目标值在数组中的 起始位置和结束位置。如果目标值不存在于数组中，返回 {-1, -1}。

示例：

• 输入：nums = [5,7,7,8,8,10], target = 8
• 输出：[3,4]

关键点

• 数组是 排序的，可以通过二分查找优化查找效率。
• 需要分别找到目标值的第一个出现位置和最后一个出现位置。

🫘2. 讲解算法原理

(1) 找第一个位置

• 使用二分查找找到目标值第一次出现的位置。
• 每次计算中间位置 mid：
  • 如果 nums[mid] < target，说明目标值在右侧，调整左边界 left = mid + 1。
  • 否则（nums[mid] >= target），目标值在左侧或当前值可能是第一个位置，调整右边界 right = mid。
• 循环结束时，检查 nums[left] 是否等于目标值，如果不等于，说明目标值不存在。

(2) 找最后一个位置

• 使用二分查找找到目标值最后一次出现的位置。

• 每次计算中间位置 mid：

  • 如果 nums[mid] <= target，说明目标值在右侧或当前值可能是最后一个位置，调整左边界 left = mid。
  • 否则（nums[mid] > target），调整右边界 right = mid - 1。

• 注意在计算 mid 时，向上取整以避免死循环：

  mid = left + (right - left + 1) / 2;
  

🫘3. 编写代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};

        // 先找第一个
        int begin;
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        // 判断是否有结果
        if(nums[left] == target) begin = left;
        else return {-1, -1}; 

        // 再找最后一个
        right = nums.size() - 1; 
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, right};
    }
};

🫘4. 总结二分模板

二分查找的关键在于调整左右边界，根据查找目标的性质选择合适的条件。

模板1：查找某个条件满足的最小值

while(left < right){
    int mid = left + (right - left) / 2;
    if(满足条件) right = mid; // 收缩右边界
    else left = mid + 1;      // 收缩左边界
}

• 最后 left 即为最小值的位置。

模板2：查找某个条件满足的最大值

while(left < right){
    int mid = left + (right - left + 1) / 2; // 向上取整
    if(满足条件) left = mid;  // 收缩左边界
    else right = mid - 1;    // 收缩右边界
}

• 最后 left 即为最大值的位置。

🌶️三、x 的平方根

题目链接：https://leetcode.cn/problems/sqrtx/description/

🫘1. 题目解析

题目描述：

计算并返回非负整数 x 的平方根的整数部分。结果必须满足：

• 如果 $r$ 是结果，那么 $r^2 \leq x $且$(r+1)^2 > x$。

示例：

• 输入：x = 8
• 输出：2（因为 $\lfloor \sqrt{8}\rfloor =2$）

约束条件：

• $x$ 是非负整数。

🫘2. 讲解算法原理

核心思想

将问题转化为在范围 [1, x] 内查找满足 $mi{d}^2\le x$ 的最大值 mid。这是一个典型的「查找最大满足某条件」的问题，适合二分查找。

详细步骤

1. 边界处理

   • 如果 $x<1$，直接返回 0，因为非负整数的平方根至少是 0。

2. 初始化查找范围

   • 定义左边界 left = 1 和右边界 right = x。

3. 二分查找

   • 计算中间值 mid:

     mid = left + (right - left + 1) / 2;  // 向上取整，避免死循环
     

   • 检查平方值：

     • 如果 $mi{d}^2\le x$，说明 mid 是一个可能的解，将左边界收缩为left=mid。
     • 否则（$mi{d}^2>x$），说明 mid 太大，将右边界收缩为 right=mid−1。

4. 结束条件

   • 二分查找结束时，left 指向满足 $lef{t}^2\le x$ 的最大值。

特殊优化

由于 $mid\times mid$ 可能会超出整数范围，mid 使用 long long 类型避免溢出。

🫘3. 编写代码

class Solution {
public:
    int mySqrt(int x) {
        if(x < 1) return 0;
        int left = 1, right = x;
        while(left < right){
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        ret

🌶️四、搜索插入位置

题目链接：https://leetcode.cn/problems/search-insert-position/description/

🫘1. 题目解析

在一个按非递减顺序排序的数组 nums 中，查找目标值 target，返回目标值的索引。如果目标值不存在于数组中，返回它 应插入的位置，以保证数组仍然是有序的。

示例：

• 输入：nums = [1,3,5,6], target = 5
• 输出：2

约束条件：

• 数组是有序的。
• 时间复杂度要求 $O(\log n)$，提示需要使用二分查找。

🫘2. 讲解算法原理

核心思想

通过二分查找找到满足 nums[mid] >= target 的最小索引，即：

• 如果数组中存在 target，此索引即为 target 的位置。
• 如果数组中不存在 target，此索引即为 target 的插入位置。

二分查找详细步骤

1. 初始化查找范围

   • 定义左边界 left = 0 和右边界 right = nums.size()。

2. 二分查找过程

   • 计算中间值 mid：

     mid = left + (right - left) / 2;
     

   • 检查 nums[mid] 的值：

     • 如果 nums[mid] < target，说明目标值在右侧，调整左边界：

       left = mid + 1;
       

     • 否则，目标值可能在当前或左侧，调整右边界：

       right = mid;
       

3. 查找结束条件

   • 循环结束时，left 等于 right，此位置即为 target 的位置或插入位置。

🫘3. 编写代码

class Solution {
public:
    int searchInsert(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) left = mid + 1;
            else right = mid;
        }
        if(nums[right] < target) return right + 1;
        return right;
    }
};

🌶️五、山脉数组的峰顶索引

题目链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/

🫘1. 题目解析

找到山脉数组的 峰值索引。山脉数组定义为：先递增后递减的数组。

示例：

• 输入：arr = [0, 2, 1, 0]
• 输出：1（峰值索引是 1）

约束条件

• 山脉数组 arr 总是合法的（至少包含一个峰值）。
• 峰值定义为满足 arr[i-1] < arr[i] > arr[i+1] 的元素。

🫘2. 讲解算法原理

通过二分查找来缩小峰值所在的范围：

1. 对于任意位置 mid：
   • 如果 arr[mid] > arr[mid + 1]：
     • 峰值一定在 mid 或 mid 的左侧（包括 mid）。
     • 调整右边界：right = mid。
   • 否则（arr[mid] < arr[mid + 1]）：
     • 峰值一定在 mid 的右侧（不包括 mid）。
     • 调整左边界：left = mid + 1。
2. 二分查找的收敛性：
   • 每次迭代中，区间 [left, right] 会缩小至最终的峰值位置。

🫘3. 编写代码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1; 
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid - 1] < arr[mid]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

结语

二分查找作为经典算法的代表，不仅展示了算法设计的精妙之处，也凸显了时间复杂度优化的重要性。通过学习和实践，您可以将其运用到更广泛的问题中，为解决实际挑战提供高效的解决方案。希望本文能够为您提供清晰的理解，并激发对算法研究的更多兴趣。

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！