简介

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法

工作原理

以在一个升序数组中查找一个数为例。
它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

整数二分

  1. // 检查x是否满足某种性质
  2. bool check(int x) {
  4. }
  5. // 找出左边最符合的
  6. int binary_search1(int l,int r) {
  7.     while (l < r) {
  8.         int mid = l + r >> 1;
  9.         if (check(mid)) r = mid;
  10.         else l = mid + 1;
  11.     }
  12.     return l;
  13. }
  14. // 找出右边最符合的
  15. int binary_search2(int l,int r) {
  16.     while (l < r) {
  17.         int mid = l + r + 1 >> 1;
  18.         if (check(mid)) l = mid;
  19.         else r = mid - 1;
  20.     }
  21.     return l;
  22. }

浮点数二分

  1. // 检查x是否满足某种性质
  2. bool check(double x) {
  4. }
  6. double binary_search(double l,double r) {
  7.     const double eps = 1e-6;     // eps 表示精度，取决于题目对精度的要求
  8.     while (r - l > eps) {
  9.         double mid = (l + r) / 2;
  10.         if (check(mid)) r = mid;
  11.         else l = mid;
  12.     }
  13.     return l;
  14. }

STL的二分查找

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中，返回值为迭代器，二者均采用二分实现，所以调用前必须保证元素有序。

  1. int main()
  2. {
  3.     vector<int> a = {1,3,5,7,9,2,4,6,8,10};
  4.     sort(a.begin(),a.end());   // 调用前必须保证元素有序
  5.     cout << *lower_bound(a.begin(),a.end(),5) << endl;
  6.     cout << *upper_bound(a.begin(),a.end(),5) << endl;
  7.     return 0;
  8. }

三分法

三分法可以用来查找凸函数的最值

  1. vector<int> arr = {1,2,5,7,11,14,16,17,20,22,25,28,30,33,35,38,40,42,46,50,53,57,58,60, 55, 44, 33, 22, 11 , 10, 7, 6, 5, 1};
  2. int trisection_search(int l,int r){
  3.     while (l < r) {
  4.         int lmid = l + (r - l) / 3;
  5.         int rmid = r - (r - l) / 3;
  6.         if ( arr[lmid] > arr[rmid]) {
  7.             r = rmid - 1;
  8.         }else {
  9.             l = lmid + 1;
  10.         }
  11.     }
  12.     return l;
  13. }
  15. int main()
  16. {
  17.     cout << arr[trisection_search(0,arr.size())] << endl;
  18.     return 0;
  19. }