lower_bound---2016级补测题----二分查找变式

以你之姓@ 2022-05-16 11:26 59阅读 0赞

lower\_bound  
Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description  
给定一个含有 n 个元素的递增序列（非严格递增）和 q 次询问，每次询问一个数，输出序列中第一个大于等于该数的元素的位置，如果序列中没有符合条件的数，则输出 “Not Found”。

Input  
输入数据有多组（数据组数不超过 20），到 EOF 结束。

对于每组数据：

第 1 行输入 2 个整数 n (1 <= n <= 10^5) 和 q (1 <= q <= 10^5)，表示序列长度和询问次数  
第 2 行输入 n 个用空格隔开的整数 Ai (0 <= Ai <= 10^9)，表示这个序列  
接下来输入 q 行，每行输入 1 个整数 x (0 <= x <= 10^9)，表示要询问的数  
Output  
对于每组数据中的每次询问，输出一行：如果序列中第一个大于等于该数的元素存在，则输出其位置，否则输出 “Not Found”（不包括引号）。

Sample Input  
5 4  
1 2 3 3 5  
1  
3  
4  
6  
Sample Output  
1  
3  
5  
Not Found  
Hint  
示例解释：

询问 1：找到第一个大于等于 1 的数为 1，在序列中的位置为 1

询问 3：找到第一个大于等于 3 的数为 3，在序列中的位置为 3

询问 4：找到第一个大于等于 4 的数为 5，在序列中的位置为 5

询问 6：序列中无法找到任何大于等于 6 的数  
注：数据量较大，请使用高效查找算法

#include<stdio.h>
    #include<stdlib.h>
    int a[100010];
    int F(int left,int right,int key)
    {
        int ans=-1,mid;
        while(left<=right)
        {
            mid =(right+left)/2;
            if(a[mid]>=key)
            {
                ans = mid;
                right = mid-1;
            }
            else left = mid+1;
        }
        return ans;
    }
    int main()
    {
        int n, q,i,m,x;
        while(scanf("%d %d",&n,&q)!=EOF)
        {
            for(i = 1; i<=n; i++)
            {
                scanf("%d",&a[i]);
            }
            while(q--)
            {
                scanf("%d",&x);
    
                m = F(1,n,x);
                if(m==-1)
                    printf("Not Found\n");
                else printf("%d\n",m);
            }
        }
        return 0;
    }

详解：假如这个数比最大的值还大，那么一直循环下面的else语句，直到left和right都等于最大值，期间ans没有增加，也就是返回值为-1；假如直接找到，没问题直接返回坐标即可，但是如果没有这个值？ 比如：最后left 指在 4，right 指在 9，序号分别是1,2，应该返回2，看一下代码，应该是这样操作的：取中间值（1+2）/2==1;a\[1\]==4