C++如何实现二分查找？C++ binary_search用法是什么

二分查找是一种在有序数组中查找特定元素的高效算法，时间复杂度为O(log n)，相比顺序查找效率提升明显。C++中既可以通过手动编写逻辑实现二分查找，也可以直接使用标准库提供的binary_search函数完成查找操作。

手动实现C++二分查找

手动实现二分查找的核心思路是维护查找区间的左右边界，每次取区间中间元素与目标值比较，根据比较结果缩小查找区间，直到找到目标值或者区间为空。

以下是迭代版本的二分查找实现代码：

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

// 二分查找函数，返回目标值的索引，未找到返回-1
int binarySearch(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        // 防止left+right溢出，等价于(left+right)/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 = binarySearch(arr, target);
    if (result != -1) {
        cout << "找到目标值，索引为：" << result << endl;
    } else {
        cout << "未找到目标值" << endl;
    }
    return 0;
}

如果需要查找目标值第一次出现的位置，可以调整逻辑，当nums[mid] == target时不直接返回，而是继续向左收缩区间：

// 查找目标值第一次出现的索引
int binarySearchFirst(const vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
    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++ binary_search用法

C++标准库的<algorithm>头文件中提供了binary_search函数，该函数可以直接判断有序区间中是否存在目标值，无需手动编写查找逻辑。

binary_search的函数原型如下：

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);

template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);

第一个版本使用默认的operator<进行比较，要求区间内的元素按升序排列；第二个版本可以传入自定义的比较函数，支持自定义排序规则。
以下是binary_search的使用示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    // 判断7是否存在于数组中
    bool hasSeven = binary_search(arr.begin(), arr.end(), 7);
    if (hasSeven) {
        cout << "数组中存在7" << endl;
    } else {
        cout << "数组中不存在7" << endl;
    }

    // 判断8是否存在
    bool hasEight = binary_search(arr.begin(), arr.end(), 8);
    if (hasEight) {
        cout << "数组中存在8" << endl;
    } else {
        cout << "数组中不存在8" << endl;
    }
    return 0;
}
binary_search与lower_bound的区别
很多开发者会混淆binary_search和lower_bound的用法，两者的核心区别在于返回值不同：
binary_search只返回布尔值，告知目标值是否存在，无法获取目标值的位置
lower_bound返回指向第一个大于等于目标值的元素的迭代器，如果需要获取目标值的位置，可以使用该函数
以下是lower_bound获取目标值位置的示例：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 7, 9, 11};
    int target = 7;
    // 找到第一个大于等于7的元素迭代器
    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        cout << "目标值第一次出现的索引为：" << (it - arr.begin()) << endl;
    } else {
        cout << "未找到目标值" << endl;
    }
    return 0;
}
使用注意事项
无论是手动实现二分查找还是使用binary_search，都需要保证操作的数据区间是有序的，否则查找结果会出错。如果数据未排序，需要先使用sort函数进行排序，再执行二分查找操作。
另外，手动实现二分查找时要注意中间值的计算方式，避免left + right出现整数溢出问题，推荐使用left + (right - left) / 2的方式计算中间索引。
	

	  

	   
	  
	
	


binary_searchC++二分查找lower_bound修改时间：2026-06-11 01:33:20