二分查找

简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

——百度百科

• 有序排列

  sort (a + 1, a + n + 1, cmp);

• 时间复杂度 O(logn)

学了二分以后给我的感觉就是很多东西都可以拿来二分，以前以为只有查找可以用二分，现在知道原来很多有范围的东西，都可以用二分来逼近答案。

整数二分

找 >= s 的数中最小的

• 记录答案

  bool check (int x)
  {
      if (a[x] >= s) return 1;
      else return 0;
  }
  
  int l = 1, r = n, ans = 0;
  while (l <= r)
  {
      int mid = (l + r) / 2;
      if (check (mid))
      {
          ans = mid;
          r = mid - 1;
      }
      else l = mid + 1;
  }
  printf ("%d", a[ans]);

• 不记录答案 · r 逼近答案

  int l = 1, r = n;
  while (l < r)
  {
      int mid = (l + r) / 2;
      if (a[mid] >= s) r = mid;
      else l = mid + 1;
  }
  printf ("%d", a[r]);

• 如果 a[mid] >= s 成立，接下来应该向左继续查找，而此时 mid 是符合要求的，所以要保留，因此 r = mid

• 如果 a[mid] >= s 不成立，接下来应该向右继续查找，而此时 mid 是不符合要求的，所以要舍弃，因此 l = mid + 1

• 输出的数一定是要符合要求的，每次查找 r = mid，r一定是符合要求，而 l 不一定，所以输出 r

找 < s 的数中最大的

• 记录答案

  bool check (int x)
  {
      if (a[x] < s) return 1;
      else return 0;
  }
  
  int l = 1, r = n, ans = 0;
  while (l <= r)
  {
      int mid = (l + r) / 2;
      if (check (mid))
      {
          ans = mid;
          l = mid + 1;
      }
      else r = mid - 1;
  }
  printf ("%d", a[ans]);

• 不记录答案 · l 逼近答案

  int l = 1, r = n;
  while (l < r)
  {
      int mid = (l + r + 1) / 2;
      if (a[i] < s) l = mid;
      else r = mid - 1;
  }
  printf ("%d", a[l]);

• 如果 a[mid] < s 成立，接下来应该向右继续查找，而此时 mid 是符合答案的，所以要保留，因此 l = mid

• 如果 a[mid] < s 不成立，接下来应该向左继续查找，而此时 mid 是不符合答案的，所以要舍弃，因此 r = mid - 1

• 输出的数一定是要符合要求的，每次查找 l = mid，l一定是符合要求，而 r 不一定，所以输出 l

浮点二分

浮点二分只能用记录答案方法，而且要设置一个范围使得查找能退出循环

const double eps = 1e-8;
double l = 0, r = n;
while (r - l > eps)
{
    double mid = (l + r) / 2;
    if (check (mid))
    {
        ans = mid;
        r = mid;
    }
    else l = r;
}
printf ("%d", ans);

习题

A Can you solve this equation? · HDU 2199

B Dating with girls(1) · HDU 2578

C Aggressive cows · POJ 2456

D Pie · POJ 3122

E River Hopscotch · POJ 3258

F 4 Values whose Sum is 0 · POJ 2785

G Defuse the Bombs · Gym 102822D