【基础算法】二分查找

二分查找

什么是二分？将问题分成两个部分。

猜数游戏

计算机给你一个范围内的随机数，你要输入一个数，计算机给你反馈是太大了还是太小了，直到你输出正确的答案。

怎么设计这个程序呢？

#include<iostream>
#include<ctime>
using namespace std;
int main()
{
    srand(time(NULL));
    int t = rand() % 100 + 1;
    int x;
    cout << "请输入一个数字：";
    cin >> x;
    while (x != t)
    {
        if (x > t)
        {
            cout << "您输入的数字太大了!" << endl;
        }
        else
        {
            cout << "您输入的数字太小了!" << endl;
        }
        cout << "请输入一个数字：";
        cin >> x;
    }
    cout << "恭喜你猜对了！";
    return 0;
}

是不是我们在系统给出提示的基础上判断了这个数所在的区间呢。这样我们就可以不断缩小区间，找到这个数。

提问：我们是随便输入的这个区间里的数字吗？

提问：如果换成不是有序的序列，我们还能这样猜吗？

所以，二分的条件是：单调有序序列、将问题划分为可行域和不可行域。

二分的常用模版：

while (l <= r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid - 1;
    else l = mid + 1;
}

跳出循环后的 \(l\) 和 \(r\) 代表什么意思呢？

例一：P2249 查找

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m;
int a[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		int l = 1, r = n;
		while (l <= r)
		{
			int mid = l + r >> 1;
			if (a[mid] >= x) r = mid - 1;
			else l = mid + 1;
		}
		if (a[l] == x) cout << l << " ";
		else cout << -1 << " ";
	}
	return 0;
}

例二：P1918 保龄球

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
struct Node
{
	int num, id;
} s[N];

bool cmp(Node &n1, Node &n2)
{
	return n1.num < n2.num;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		//s[i] = {num, i};
		s[i].num = num;
		s[i].id = i;
	}
	sort(s + 1, s + 1 + n, cmp);// 按数量升序排列
	cin >> m;
	while (m --)
	{
		int x;
		cin >> x;
		int l = 1, r = n;
		while (l <= r)
		{
			int mid = l + r >> 1;
			//cout << mid << endl;
			if (s[mid].num < x) l = mid + 1;
			else r = mid - 1;
		}
		if (s[l].num == x) cout << s[l].id << endl;
		else cout << 0 << endl;
	}
	return 0;
}