二分查找&二分答案

二月 06, 2018 2060

O(\log_2n) 的优秀算法

二分查找

百度百科原话

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

二分查找的时间复杂度是 O(log_{2}n)

要求

  • 查找的序列必须采用顺序存储结构
  • 查找的序列必须是有序排列的

思路

  1. 将需要查找的序列进行排序（一般为升序排列）

  2. 将序列中间位置记录的元素与关键字比较

  3. 如果相等，则返回查找成功
    如果不相等，则将序列分成左右两个子序列，若元素小于关键字，就到左子序列中查找；否则就到右子序列中查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline bool BinarySearch(int l,int r,int t,int x[]){
  while (l <= r){
    int mid = (l + r) >> 1;
    if (x[mid] == t) return true;
    if (x[mid] < t) l = mid + 1;
    if (x[mid] > t) r = mid - 1;
  }
  if (l > r) return false;
}
int main(){
  int dest;
  cin >> dest;
  int n;
  cin >> n;
  int *p = new int[n + 1];
  for (int i = 0;i < n;i++) cin >> p[i];
  printf("%s\n",BinarySearch(0,n - 1,dest,p)?"YES":"NO");
  return 0;
}

二分答案

看完了二分查找，你会发现二分好像只能用来在有序数列里找数。

对，一些情况二分只能拿来找数，但是从它身上衍生出来的二分答案却是一个很有用的东西！

二分答案，就是通过二分查找的方式枚举出一个答案来，然后再验证你的查找结果是否正确，从而获取答案

要求&特点

  1. 答案具有单调性
  2. 题面里包含与“最小的最大，最大的最小”相关的字眼

思路

  1. 先将给定的序列排序

  2. 参照二分查找，枚举一个答案mid

  3. 验证这个答案是否可行

  4. 如果可行，更新边界，找寻更佳答案
    如果不可行，更新边界，继续寻找答案

代码实现

一般模板

其中的check函数需要针对每一个题目进行验证

当然你会写暴力枚举的check也可以借鉴过来#(滑稽)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline bool check(int x){
  /* code here*/
  return true;
}

int main(int argc, char const *argv[]) {
  int n,m;
  cin >> n >> m;
  int *p = new int[n + 2];
  for (int i = 0;i < n;i++) cin >> p[i];
  // -----------------------------------
  int l = 0,r = n - 1;
  int ans = 0;
  while (l <= r){
    int mid = (l + r) >> 1;
    if (check(ans)){
      l = mid + 1;
      ans = mid;
    }
    else r = mid - 1;
  }
  cout << ans << endl;
  // -----------------------------------
  return 0;
}

推荐题目

  1. 「洛谷P2678 跳房子」 出处：NOIP2015 提高组
  2. 「洛谷P1824 进击的奶牛」 出处：USACO