C++中如何实现二分查找算法

二分查找是一种针对有序序列的高效查找算法，核心思路是通过不断缩小查找区间，每次将查找范围缩小一半，最终定位到目标元素的位置。在C++中实现二分查找需要保证待查找的序列是升序或降序排列的，否则无法得到正确结果。

二分查找的实现前提

使用二分查找之前需要满足两个核心条件：

• 待查找的序列必须是已经排好序的，通常默认是升序序列，如果是降序序列需要微调比较逻辑。
• 序列需要支持随机访问，比如数组、vector等容器，链表这类不支持随机访问的容器不适合使用二分查找。

迭代方式实现二分查找

迭代实现是二分查找最常用的实现方式，通过维护左右两个边界指针，不断调整区间范围，直到找到目标元素或者区间为空。

#include <iostream>
#include <vector>
using namespace std;

// 迭代方式实现二分查找，返回目标元素的索引，不存在则返回-1
int binarySearchIterative(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1; // 右边界初始化为最后一个元素的索引
    while (left <= right) {
        // 计算中间索引，避免(left + right)溢出，使用left + (right - left) / 2
        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; // 遍历完区间未找到目标元素
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int result = binarySearchIterative(arr, target);
    if (result != -1) {
        cout << "找到目标元素，索引为：" << result << endl;
    } else {
        cout << "未找到目标元素" << endl;
    }
    return 0;
}

递归方式实现二分查找

递归实现二分查找的思路和迭代一致，只是把区间调整的逻辑放到递归函数中，通过递归调用不断缩小查找范围。

#include <iostream>
#include <vector>
using namespace std;

// 递归辅助函数，接收当前查找区间的左右边界
int binarySearchRecursiveHelper(const vector<int>& nums, int target, int left, int right) {
    if (left > right) {
        return -1; // 区间为空，未找到目标元素
    }
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        return binarySearchRecursiveHelper(nums, target, mid + 1, right);
    } else {
        return binarySearchRecursiveHelper(nums, target, left, mid - 1);
    }
}

// 对外暴露的递归二分查找接口
int binarySearchRecursive(const vector<int>& nums, int target) {
    if (nums.empty()) {
        return -1;
    }
    return binarySearchRecursiveHelper(nums, target, 0, nums.size() - 1);
}

int main() {
    vector<int> arr = {2, 4, 6, 8, 10, 12};
    int target = 8;
    int result = binarySearchRecursive(arr, target);
    if (result != -1) {
        cout << "找到目标元素，索引为：" << result << endl;
    } else {
        cout << "未找到目标元素" << endl;
    }
    return 0;
}

两种实现方式的对比

使用二分查找的注意事项

• 中间索引的计算不要直接使用(left + right) / 2，当left和right都很大时，相加可能会超出int类型的范围导致溢出，推荐使用left + (right - left) / 2的计算方式。
• 循环条件使用left <= right而不是left < right，如果写成后者，当区间只剩下一个元素时循环会直接结束，可能会漏掉对最后一个元素的判断。
• 如果序列中存在多个相同的目标元素，上述实现返回的是任意一个的索引，如果需要返回第一个或最后一个出现的位置，需要调整边界调整的逻辑。
• 对于C++标准库，已经提供了std::binary_search、std::lower_bound、std::upper_bound等现成的二分查找相关函数，实际开发中如果不需要自定义逻辑，可以直接使用这些标准库函数提升开发效率。

二分查找C++查找算法algorithm修改时间：2026-07-06 19:48:25