二分查找

[参考文献] https://www.bilibili.com/video/BV1d54y1q7k7/?share_source=copy_web&vd_source=586c54b04d52432e150fe6416a170629

二分的本质

设一个数组中有N个元素，前k个元素为蓝色，后N-k个元素为红色

但对于该数组，k的位置是未知的，即整个数组的颜色位置

我们需要求出蓝红边界，即k

朴素算法

设计一个蓝色指针，从左向右不断移动到边界或设计一个红色指针，从右到左不断移动到边界

时间复杂度：O(n)

因为指针移动是缓慢进行的，每次循环移动一次直到边界

二分查找

我们可以查询最中间元素颜色，若为蓝色，则该元素前全为蓝色，可以将蓝色指针直接拓展到该元素

重复操作，查询剩下区域最中间元素颜色，若为红色，则该元素后全为红色，可以将红色指针直接拓展到该元素

不断重复操作，直到最后找到蓝红边界

时间复杂度：O(logn)

因为每次循环中查找区域长度缩小一半，合计约logn次查找完毕

伪代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

l=-1, r=N

while l+1 != r

m = $(l+r)/2$

if (isBlue(m))

	l=m

else 

	r=m

return l or r

思路如下：

1. 初始设置l，r指针分别指向蓝色和红色区域
2. 循环体内进行二分，两指针快速向边界逼近，保持l，r颜色不改变
3. 最后l与r正好指向蓝红边界，返回一个即可

细节分析

1. 初始值为什么l是-1，r是N？

   若整个数组为同一种颜色，则对应另一颜色的指针一开始便会出错

   

   即如果哪边是开区间，则需要对应向外移动一位

2. m是否始终处于[0,N]内？

   m尽可能小即l与r尽可能小，为保证进入循环体，lmin=-1，rmin=1，则mmin=0

   m尽可能大即l与r尽可能大，为保证进入循环体，lmax=N-2，rmax=N，则mmax=N-1

   不会溢出

3. 更新指针时能不能写成l=m+1,r=m-1？

   不能，若l或r指针在蓝色最后一位或红色第一位，这种方法可能会越过蓝色与红色区域

4. 会不会死循环？

   考虑以下情况

   • l+1=r：l的下一个元素是r，while循环体直接退出

   • l+2=r：l与r间隔了一个元素，求得m为l与r间隔的元素，将l或r设置为m，即回到第一种情况

   • l+3=r：会回归到第二进而第一种情况

   • 之后的都会回归到第一种情况

     故不会

     即二分最后的分界线一定要唯一，不然返回值也不是唯一的

一般流程

1. 建模：划分蓝红区域，确定分界线、检查方式
2. 确定返回是l还是r
3. 套用算法模板
4. 加入后处理逻辑(opt)

算法模板

1
2
3
4
5
6
7
8
9
10
11
12

int bsearch(int l, int r){
    while (l <= r){
        int mid = l + ((r-l)>>1); // 计算中间值，这样写可以防止溢出
        if (check(mid)) { //若该位置符合条件，则将指针拓展至该位置
            r = mid; //右指针移动到中间
        }
        else {
            l = mid; //不符合条件下让左指针移动到中间
        }
    }
    return l; //输出答案 注意判断该位置是右指针还是左指针移动
}

递归版本（查找某数位置或存在性）：

1
2
3
4
5
6
7

int bsearch(int *arr, int target, int l, int r){
    if (l>r) return -1; //表示未找到
    int mid = l + ((r-l)>>1);
    if (arr[mid]==target) return mid;  //表示找到，在mid中
    else if (arr[mid]>target) bsearch(arr, target, l ,mid);  //在左边找
    else bsearch(arr, target, mid+1, r);  //在右边找
}

例

对于数组 3 4 4 5 5 5 6 7 下标从1开始

1. 找到第一个大于5的元素的位置下标：在最后一个5右边确认分界线，找线右侧第一个元素

   

   分界线左边的数：都<=5 分界线右边的数：都>5

   1 2 3 4 5 6 7 8 9 10 11 12

   bool isBlue(int x){ if (x<=5) return true; else return false; } while(l+1!=r){ int mid = l+r>>1; if (isBlue(q[mid])){ l=mid; } else r = mid; } return r;

2. 找到最后一个小于等于5的元素的位置下标：在最后一个5右边确认分界线1，找线左侧第一个元素

   

   1 2 3 4 5 6 7 8 9 10 11 12 13

   bool isBlue(int x){ if (x<=5) return true; else return false; } while(l+1!=r){ int mid = l+r>>1; if (isBlue(q[mid])){ l=mid; } else r = mid; } if (q[l]==5) return l; // 保证找到5 else return -1;

C++ STL

C++的stl中有两个函数可以快速实现二分查找：

头文件：#include

1. binary_search()：查找元素存在性

模板：binary_search(arr[], arr[]+size, index)

• arr[]：数组首地址
• size：数组元素个数
• index：需要查找的值

原理：在数组中进行二分检索，若在数组中查到index元素则为真否则为假

注意：要求数组中元素非递减

2. lower_bound()：查找第一个大于或等于某个元素的位置

模板：lower_bound(arr[], arr[]+size, index)

• arr[]：数组首地址
• size：数组元素个数
• index：需要查找的值

原理：在first与last的前闭后开区间中二分查找，返回大于等于index的第一个元素位置的地址，如果都小于，则返回last的位置

e.g.

3.upper_bound()：查找第一个大于某个元素的位置

模板：upper_bound(arr[], arr[]+size, index)

• arr[]：数组首地址
• size：数组元素个数
• index：需要查找到值

原理：在前闭后开区间中查找关键字的上界，返回大于index的第一个元素位置的地址，如果插入元素大于数组中全部元素，返回的是last

浮点数二分

求一个浮点数n的三次方根

浮点数由于精度较高，无法直接暴力枚举，或者用整数二分

我们可以将while循环中的条件改为精度差小于某个浮点数（如1e-8）

一般让查找要求精度比题目要求精度精一些，则最后输出l或r都可以

优化：由于浮点数的不好控制性，我们可以直接固定二分次数

如下方固定100次，完全可以将浮点数二分到一个1e-30的程度

代码

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
31
32

// 求一个数的立方根
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <iomanip>
#define ios ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e5+10;
typedef pair<int,int> PII;
double n;
bool check(double x){
  if (x*x*x<=n) return 1;  // 如果该数立方小于输入数，在更大数中寻找
  else return 0;  // 否则在更小数中寻找
}
int main(){
  cin >> n;
  double l = 0.0, r = n+1;
  //while(r-l>1e-8){  // 控制精度范围
  for(int i = 1; i<=100;i++){  // 或者可以优化为二分100次，则对于2e100次二分，完全可以把一个浮点数精确到1e-30的精确度
    double mid = (l+r)/2; 
    if (check(mid)) l = mid;
    else r = mid;

  }
  cout << floor(r);  // 这里如果精度要求没有1e-8，则输出l与r都一样
  return 0;
}