C++ 二分查找算法怎么写_C++算法面试高频题解析-C++-PHP中文网

C++ 二分查找算法怎么写_C++算法面试高频题解析

尼克

发布： 2025-11-30 15:31:16

原创

992人浏览过

<p>二分查找用于在有序数组中高效查找目标值，时间复杂度O(log n)。核心思想是每次缩小一半搜索区间，需满足数组有序且支持随机访问。标准写法使用闭区间[left, right]，循环条件为left <= right，通过mid = left + (right - left) / 2计算中点，避免整数溢出。若nums[mid] == target则返回下标；小于则搜索右半区，left = mid + 1；大于则搜索左半区，right = mid - 1。常见变体包括查找左边界和右边界：查找第一个等于target的位置时，命中后不立即返回，而是记录result = mid并继续向左搜索（right = mid - 1）；查找最后一个位置则继续向右搜索（left = mid + 1）。C++ STL提供binary_search、lower_bound（首个≥target）、upper_bound（首个>target）等函数，可简化实现。面试关键在于明确查找目标（任意位置或边界）、正确处理区间开闭与边界更新，防止死循环。掌握标准写法与两种边界变体，并熟悉STL函数，足以应对大多数面试题。</p>

c++ 二分查找算法怎么写_c++算法面试高频题解析

二分查找是一种在有序数组中快速定位目标值的高效算法，时间复杂度为 O(log n)，是 C++ 面试中最常考的基础算法之一。掌握其写法和边界处理技巧至关重要。

基本思路与适用条件

二分查找的核心思想是每次将搜索区间缩小一半：

数组必须是已排序的（默认升序）
支持随机访问（数组或 vector）
查找某个值是否存在、位置，或满足某种条件的边界

标准二分查找写法

查找目标值 target 的下标，若不存在返回 -1：

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 注意：闭区间
<pre class='brush:php;toolbar:false;'>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;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

Qwen

阿里巴巴推出的一系列AI大语言模型和多模态模型

691

查看详情

常见变体：查找左边界

当存在重复元素时，查找第一个等于 target 的位置：

int leftBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
<pre class='brush:php;toolbar:false;'>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;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

常见变体：查找右边界

查找最后一个等于 target 的位置：

int rightBound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
<pre class='brush:php;toolbar:false;'>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;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

STL 中的二分查找函数

C++ 标准库提供了几个高效的二分查找函数，面试中可简要提及：

std::binary_search：判断元素是否存在
std::lower_bound：返回第一个 ≥ target 的迭代器
std::upper_bound：返回第一个 > target 的迭代器

例如：

vector<int> nums = {1, 2, 2, 2, 3, 4};
auto it = lower_bound(nums.begin(), nums.end(), 2);
int index = it - nums.begin(); // 返回 1

登录后复制

面试注意事项

写二分查找时容易出错的地方：

循环条件是 left <= right 还是 left < right，取决于区间开闭
mid 计算用 left + (right - left) / 2 避免整数溢出
更新 left 和 right 时是否漏掉 ±1，防止死循环
明确题目是要找“任意位置”还是“边界位置”

基本上就这些。掌握标准写法和两个边界变体，再熟悉 STL 函数，应对 C++ 面试中的二分查找题就足够了。关键是逻辑清晰，边界处理正确。

以上就是C++ 二分查找算法怎么写_C++算法面试高频题解析的详细内容，更多请关注php中文网其它相关文章！

大家都在看：

C++静态库和动态库怎么做_在Linux下编译和使用C++共享库的方法 C++怎么获取当前时间戳_C++中使用chrono库处理时间和日期 c++如何实现责任链设计模式_c++解耦请求的发送者和接收者 C++的std::execution是什么_C++17并行算法策略提升STL性能 C++函数指针怎么用_C++回调函数的定义与实现方法