二分查找

建立的前提是一个有序的序列

1.划定范围

2.找中间位置

value		10	20	45	50	100	120	121	30	500	600
index	0	1	2	3	4	5	6	7	8	9	10

假设我们要去查找50

查找过程：

L = 1

R = 10

MID = (L+R)>>1

由于MID值 大于 目标50，所以

R = MID-1

L 还是呢个L

MID = (L+R)>>1

由于MID 值小于了目标50，所以要把L往右边移动

L = MID + 1

R还是呢个R

MID = (L+R)>>1

此时我们会发现 L 的值为3 R值为4 MID 值为3

由于MID 对应的值小于了目标50，所以要把L往右边移动

再次移动后我们会发现什么？？？？？

L 在 4这个位置

R 在 4这个位置

MID 必然也会在4这个位置，因为MID 是由L\R算出来的

现在假设我们要找55，找55的话L再次移动会怎么样，思考一下

讲一下对数的概念：

二分查找的时间复杂度为

$$
log2n
$$

二分查找常见问题

1. 二分查找元素x在数列中是否存在
1. 二分查找左边界：第一次出现的位置（>=该元素的第一个数的位置）
1. 二分查找右边界：最后一次出现的位置（>该元素的第一个元素的位置）

P1272 二分查找模板

#include<bits/stdc++.h>
using namespace std;
const int N = 1000100;//数组范围常量
int a[N];
int x,n;
int main() {
    //cin>>n; 数据量大的题目我们尽量用scanf
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    
    //二分循环
    //定义边界
    int l = 1,r = n,mid;
    
    while(l <= r){
        mid = (l+r)>>1;
        if(x < a[mid]){
            r = mid - 1;
        }else if(x > a[mid]){
            l = mid + 1;
        }else if(x == a[mid]){
            cout<<mid;
            return 0;//我也可以写break 
            //但是break会导致我后面再用标记变量去处理
        }
    }
    cout<<-1;
}

注意:

求 mid 的3种写法 (1)mid=(l+r)/2

(2)mid=(l+r)>>1(括号可以不写)

(3)mid=l+(r-l)/2(可以防止 |+r 越界的情况 ,数学原理上跟第一个一样，但是没有先加起来)

左闭右开的写法

有些人或者老师喜欢教左闭右开，我这里教的是闭区间

左闭右开的优势：1.算数好算 2.连续的区间表达

[1,2] 实际上是两个数

[1,3)直接3-1就好了

考虑方面 闭区间 更好考虑

科学方面 左闭右开 更科学

#include<bits/stdc++.h>
using namespace std;
const int N = 1000100;//数组范围常量
int a[N];
int x,n;
int main() {
    //cin>>n; 数据量大的题目我们尽量用scanf
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    
    //二分循环
    //定义边界
    int l = 0,r = n+1,mid;
    
    while(l < r){
        mid = (l+r)>>1;
        if(x < a[mid]){
            r = mid;
        }else if(x > a[mid]){
            l = mid + 1;
        }else if(x == a[mid]){
            cout<<mid;
            return 0;//我也可以写break 
            //但是break会导致我后面再用标记变量去处理
        }
    }
    cout<<-1;
}

二分查找左边界 L > R 停止查找

P1819 二分查找左边界（第一次出现）

value		10	10	30	30	30	30	30	30	40	40
index	0	1	2	3	4	5	6	7	8	9	10

模拟一下分别查找 30、10、40、15、50

我们会发现第一个问题，如果直接模拟，就会导致mid就是我们要找的目标

所以通过模拟得知 L > R 停止查找

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int a[N];
int n, q; //n个数字 q次询问
//目标：
//求元素x在数组中首次出现的位置
int fun(int x) {
    //确定好边界
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = (l + r)/2;
        if (x < a[mid]) r = mid - 1;
        else if (x > a[mid]) l = mid + 1;
        else if (x == a[mid]) r = mid - 1;
    }
    if (a[l] == x) return l;
    else return -1;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> q;
    int x;
    for (int i = 1; i <= q; i++) {
        cin >> x;
        cout << fun(x) << " ";
    }
}

P1820 二分查找右边界（最后一次出现）

value		10	10	30	30	30	30	30	30	40	40
index	0	1	2	3	4	5	6	7	8	9	10

找30

自己来模拟一下