二分查找算法详解与经典例题解析 | 极客日志

C++算法

二分查找算法详解与经典例题解析

系统讲解了二分查找算法的核心原理及多种变体应用。涵盖基础二分查找、查找元素首尾位置、搜索插入位置、计算平方根、寻找山峰数组峰顶、寻找峰值、旋转排序数组最小值以及缺失数字问题。通过对比暴力解法与二分优化方案，分析了时间复杂度为 O(log n) 的实现细节，包括指针移动逻辑、边界条件处理及防止溢出的技巧。适合希望深入理解二分查找应用场景的开发者阅读。

人间失格发布于 2026/3/28更新于 2026/4/176 浏览

二分查找算法详解与经典例题解析

1. 二分查找

题目链接：704. 二分查找

题目描述：

给定一个升序排列的整数数组 nums，和一个目标值 target。如果 target 在数组中存在，返回其下标；否则，返回 -1。

示例 1：

输入：nums = [-1,0,3,5,9,12], target = 9
输出：4
解释：9 出现在 nums 中，并且下标为 4。

示例 2：

输入：nums = [-1,0,3,5,9,12], target = 2
输出：-1
解释：2 不存在 nums 中，因此返回 -1。

提示：

你可以假设数组中的所有元素是互不相同的。
数组 nums 的长度范围为 [1, 10000]。
数组 nums 的每个元素都在 [-9999, 9999] 之间。

解题思路

方法一：暴力遍历

从前往后遍历数组，遇到与 target 相等的数，返回下标。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
};

但是这种方法时间复杂度是 O(n) ，且没有利用到数组的有序性，略不足。

方法二：二分查找

利用数组的有序性，先从数组的中间位置的数开始比较，根据比较结果将数组的查找范围缩小。

具体过程如下：

初始化 left 和 right 指针分别指向数组的开头和末尾。
计算中间位置。（计算过程中结果可能会溢出，不采用。）

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

mid = left + (right - left) / 2

mid = (left + right) / 2

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        // 当 left == right 时还需要比较
        while (left <= right) {
            // 计算中间值的下标，注意防溢出
            int mid = (right - left) / 2 + left;
            if (target > nums[mid]) left = mid + 1;
            else if (target < nums[mid]) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return {-1, -1};
        int left = 0, right = nums.size() - 1;
        int mid = 0;
        // 1. 查找左端点
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        // 2. 判断目标值是否在数组
        int Leftpoint = 0; // 用于记录左端点
        if (nums[left] != target) return {-1, -1};
        else Leftpoint = left;
        // 3. 查找右端点
        // 程序走到这说明找到了目标值左端点，只需要更新 right 即可开始新一轮的查找
        right = nums.size() - 1;
        while (left < right) {
            mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        return {Leftpoint, right};
    }
};

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 查找大于等于 target 区间的左端点
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        // 边界情况的处理，当数组的元素全部小于 target 时
        // 结束循环时，left == n - 1（n 为数组元素的大小）
        if (nums[left] < target) return left + 1;
        return left;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        // 由于两个较大的数相乘可能会超过 int 最大范围，因此用 long long
        long long i = 0;
        for (i = 0; i <= x; i++) {
            // 如果两个数相乘正好等于 x，直接返回 i
            if (i * i == x) return i;
            // 如果第一次出现两个数相乘大于 x，说明结果是前一个数
            if (i * i > x) return i - 1;
        }
        // 为了处理 oj 题需要控制所有路径都有返回值，防止编译报错
        return -1;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        // 对 x 为 0 的情况特殊处理
        if (x == 0) return 0;
        // 查找 i 的平方小于等于 x 区间的右端点
        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;
        }
        return left;
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n - 1; i++) {
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                return i; // 找到峰顶，返回索引
            }
        }
        return -1; // 为了防止编译报错，所有路径必须有返回值
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 因为峰顶元素不会在开头和结尾，所以从 1 和 n-2 开始查找
        int left = 1, right = arr.size() - 2;
        // 查找上升趋势区间的右端点的写法
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        // 查找下降趋势区间的左端点的写法
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        // 查找下降趋势区间的左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        // 查找查找上降趋势区间的右端点
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        // 选定最后一个值为基准值
        int left = 0, right = nums.size() - 1;
        int last = nums[right]; // 基准值
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > last) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        // 最后一个同学的学号
        int n = records.size();
        // 哈希表
        int hash[10001] = {0};
        for (auto e : records) hash[e]++;
        // 遍历哈希表查找缺失的元素
        for (int i = 0; i <= n; ++i) {
            if (hash[i] == 0) return i;
        }
        // 保证所有路径都有返回值
        return -1;
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        for (int index = 0; index < records.size(); index++) {
            if (records[index] != index) return index;
        }
        // 特殊处理缺失的元素有可能就是最后一个元素的情况
        return records.size();
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        // 不缺失的情况下最后一个元素
        int LastElement = records.size();
        int target = 0;
        for (int i = 0; i <= LastElement; ++i) target ^= i;
        for (auto e : records) target ^= e;
        return target;
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int LastElement = records.size();
        // 等差数列求和
        int sum = LastElement * (LastElement + 1) / 2;
        for (auto e : records) sum -= e;
        return sum;
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        // 特殊处理缺失最后一个数的情况
        return records[left] == left ? left + 1 : left;
    }
};