二分查找学习笔记

二分查找学习笔记

最近在学习二分。

然后遇到一题：题目 - T^T online Judge

二分法

Problem Description

二分查找的基础

Input

多组测试数据

每组测试数据的第一行输入n，m表示数组的长度和询问的次数(1<=n,m<=105)

接下来一行是n个数字A0...An-1 满足 Ai<=Ai+1 (1<=Ai<=109)

然后输入m行，每行是一个数字Qi表示询问(1<=Qi<=109)

Output

对于每个询问，如果Qi在数组中出现过，输出两个数字分别第一次出现和最后一次出现的位置，如果Qi在数组中没有出现，则输出一个数字表示第一个大于Qi的数字的位置（如果没有任何数字大于Qi则输出n）

SampleInput

10 4 
3 3 3 5 5 5 6 7 7 7 
1 
5 
6 
10

SampleOutput

0 
3 
5 
6 
6 
10

#include

#define LL long long

LL half_search_end(LL *a, LL n, LL num)    // 取第一个比num大的位置
{
    LL start = -1;
    LL end = n;
    while (1)
    {
        LL mid = (start + end) / 2;
        if (mid == start || mid == end) return end;    // mid 最后一定会等于 start 或 end
        if (a[mid] > num) end = mid;
        else start = mid;
    }
}

LL half_search_start(LL *a, LL n, LL num)    // 取最后一个比 num 小的位置
{
    LL start = -1;
    LL end = n;
    while (1)
    {
        LL mid = (start + end) / 2;
        if (mid == start || mid == end) return start;
        if (a[mid] < num) start = mid;
        else end = mid;
    }
}

int main()
{
    LL n, m;
    while (scanf("%lld %lld", &n, &m) != EOF)
    {
        LL a[100005];
        for (LL i = 0; i < n; i++)
        {
            scanf("%lld", &a[i]);
        }
        for (LL i = 0; i < m; i++)
        {
            LL num;
            scanf("%lld", &num);
            LL res = half_search_end(a, n, num);
            if (a[res - 1] == num)    // 若出现 num，则 res-1 为最后一个 num 的位置
            {
                printf("%lld %lldn", half_search_start(a, n, num) + 1, res - 1);
            }
            else
            {
                printf("%lldn", res);
            }
        }
    }
    return 0;
}

其中的两个函数可以当模板使用。

对这两个函数的结果进行处理可以应用在更多的地方。