C语言中的binary_search()函数是如何实现二分查找并详细解析其内部工作原理的？

本文共计991个文字，预计阅读时间需要4分钟。

pythondef binary_search(arr, target): 查找目标元素是否在指定区间内 参数: arr: 有序列表 target: 要查找的目标元素 返回: bool: 目标元素是否在区间 [first, last] 内 first, last=0, len(arr) - 1 while first <=last: mid=(first + last) // 2 if arr[mid] target: last=mid - 1 else: return True return False

binary_search()函数定义在<algorithm>头文件中，用于查找指定区域内是否包含某个目标元素。

该函数有 2 种语法格式，分别为：

//查找 [first, last) 区域内是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last, const T& val); //根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); 其中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于指定要查找的目标值；comp 用于自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

同时，该函数会返回一个 bool 类型值，如果 binary_search() 函数在 [first, last) 区域内成功找到和 val 相等的元素，则返回 true；反之则返回 false。

需要注意的是，由于 binary_search() 底层实现采用的是二分查找的方式，因此该函数仅适用于“已排好序”的序列。所谓“已排好序”，并不是要求 [first, last) 区域内的数据严格按照某个排序规则进行升序或降序排序，只要满足“所有令 element<val（或者 comp(val, element）成立的元素都位于不成立元素的前面（其中 element 为指定范围内的元素）”即可。

有关二分查找算法，读者可阅读《二分查找算法》一节。

举个例子：

#include <iostream> // std::cout #include <algorithm> // std::binary_search #include <vector> // std::vector using namespace std; //以普通函数的方式定义查找规则 bool mycomp(int i, int j) { return i > j; } //以函数对象的形式定义查找规则 class mycomp2 { public: bool operator()(const int& i, const int& j) { return i > j; } }; int main() { int a[7] = { 1,2,3,4,5,6,7 }; //从 a 数组中查找元素 4 bool haselem = binary_search(a, a + 9, 4); cout << "haselem：" << haselem << endl; vector<int>myvector{ 4,5,3,1,2 }; //从 myvector 容器查找元素 3 bool haselem2 = binary_search(myvector.begin(), myvector.end(), 3, mycomp2()); cout << "haselem2：" << haselem2; return 0; } 程序执行结果为：

haselem：1
haselem2：1

此程序中演示了 binary_search() 函数的 2 种适用场景，其中 a[7] 数组中存储的为升序序列；而 myvector 容器中存储的序列虽然整体是乱序的，但对于目标元素 3 来说，所有符合 mycomp2(element, 3) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此 binary_search() 函数仍可正常执行。

C++ STL标准库给出了 binary_search() 函数底层实现的参考代码（如下所示），感兴趣的读者可自行研究，这里不再赘述：

//第一种语法格式的实现 template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { first = std::lower_bound(first,last,val); return (first!=last && !(val<*first)); } //第二种语法格式的底层实现 template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& val, Compare comp) { first = std::lower_bound(first, last, val, comp); return (!(first == last) && !(comp(val, *first))); }

有关 lower_bound() 函数的功能和用法，可阅读《C++ lower_bound()函数》一节；有关 upper_bound() 函数的功能和用法，可阅读《C++ upper_bound()函数》一节。