二分查找

二分算法

整数二分

  • 和 y 总的模板一致，我们进行对二段性的分辨，然后看我们是要寻找什么值即可
  • image-20250314130701211
  • image-20250314130735988
  • image-20250314131018631
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
33
34
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

const int N = 2e5  + 9;

int a[N], n, q;

int bi_search(int x)
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid  + 1;
    }
    if(a[l] == x) return l;
    else return -1;
}

int main()
{
    scanf("%d %d", &n, &q);
    for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
    
    while(q --)
    {
		int x; scanf("%d", &x);
        printf("%d ", bi_search(x));
  	}
    return 0;
}

第二种模板，我们换个方式来分段即可

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
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 2e5 + 9;

int n, q, a[N];

int bin_search(int x)
{
   int l = 1, r = n;
   while(l < r)
   {
   	int mid = l + r + 1 >> 1; // 注意这里我们进行上取整，防止出现死循环
   	if(a[mid] < x) l = mid;
   	else r = mid - 1;
   }
   if(a[l + 1] == x) return l + 1;
   else return -1;
}

int main()
{
   scanf("%d%d", &n, &q);
   for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
   
   while(q --)
   {
   	int x; scanf("%d", &x);
   	printf("%d ", bin_search(x));
   }
   
   return 0;
}

STL 及开区间写法

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
33
34
35
36
37
38
39
40
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;
const int N = 2e5 + 9;

int a[N], n, q;

int main()
{
    cin >> n >> q;
    for(int i = 1;i <= n;i ++) cin >> a[i];

    // 1.STL 写法
    while(q --)
    {
        int x; cin >> x;

        auto ans = lower_bound(a + 1, a + 1 + n, x) - a;
        auto ans1 = upper_bound(a + 1, a + 1 + n, x - 1) - a;
        int put = (ans == n + 1) ? -1 : ans;
        cout << put << " ";

        // 2.开区间二分写法
        int l = 0, r = n + 1;
        while(l + 1 != r)
        {
            int mid = l + r >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid;
        }
        if(r <= n && a[r] == x) cout << r << " ";
        else cout << -1 << " ";
    }
    return 0;
}


蓝桥杯真题（四平方和）

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
int n, m;
const int N = 5e6 + 9;


struct Sum
{
    int s, c, d;
    bool operator < (const Sum& t)const
    {
        if(s != t.s) return s < t.s;
        if(c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];


int main()
{
    cin >> n;
    for(int c = 0; c * c <= n;c ++)
        for(int d = 0;c * c + d * d <= n;d ++)
            sum[m ++] = {c * c + d * d, c, d};

    sort(sum, sum + m);

    for(int a = 0; a * a <= n; a ++)
        for(int b = 0;a * a + b * b <= n;b ++)
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            if(sum[l].s == t)
            {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    return 0;
}