Power OJ 2460: 入门基础之二分查找

向右看齐 2021-09-28 06:26 229阅读 0赞

# [Power OJ 2460: 入门基础之二分查找][Power OJ 2460_] #

## Description ##

> 数组a\[\]有n个元素，元素值保证不降（即数组满足a1<=a2<=a3<=…<=ak<=…<=an  
> ）。你的任务是，找到数组中大于数字key的所有元素中最小的那个。

## Input ##

> 多组输入。 每组第一排有两个数字n，m，分别代表数组的元素个数和询问的次数。(1<=n,m<=10^5)  
> 第二排有n个整数，表示数组的n个元素的值。(1<=ai<=10^5) 接下来有m排，每排有一个整数key(1<=key<=10^5)

## Output ##

> 对于每组，你应该输出m排数字，第i排的数字表示第i次询问的答案，若没有这样的数字，请输出-1代替。

分析题意，本题目和二分有关，但和普通的二分不同的是在于条件的判断。  
如果按照最初的二分的条件写的话，key如果不在a数列中有相等的就要返回false。  
那么这道题需要更改的条件是什么呢。

//数组a使用的是全局变量
    void F(int key,int n)
    { 
        int x=1,y=n;//从1到n分别为数组a的下标
        int mid;
        while(x<=y)
        { 
            mid=(x+y)/2;
            if(a[mid]>key&&a[mid-1]<=key)//与a[mid]==key不同的是，本题目是寻找的是大于key的最小值，mid在本体的意义就是寻找的大于key的最小值
            { 
                cout<<a[mid]<<endl;
                break;
            }
            else if(a[mid]>key)//与最初的二分没有变化
                y=mid-1;
            else if(a[mid]<=key)//这里，与初始二分有差异的原因是因为，a[mid]的限制范围一定是个左闭右开，这跟前面的if是有关的，假设是a[mid]<key;漏掉了等于key的情况的话，那么a[mid+1]可能会出现等于key的情况。那么本体就没有输出了
                x=mid+1;
        }
    }

针对输出为-1的情况，有且仅有key大于等于数组a的最后一项，此处不再赘述。  
要点就是这些，样例代码如下

#include<bits/stdc++.h>
    using namespace std;
    int a[100005];
    void F(int key,int n)
    { 
        int x=1,y=n;
        int mid;
        while(x<=y)
        { 
            mid=(x+y)/2;
            if(a[mid]>key&&a[mid-1]<=key)
            { 
                cout<<a[mid]<<endl;
                break;
            }
            else if(a[mid]>key)
                y=mid-1;
            else if(a[mid]<=key)
                x=mid+1;
        }
    }
    int main()
    { 
        int m,n,i;
        int b[100005];
        while(cin>>n>>m)
        { 
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            for(i=1; i<=n; i++)
                cin>>a[i];
            for(i=1; i<=m; i++)
                cin>>b[i];
            for(i=1; i<=m; i++)
            { 
                if(b[i]>=a[n])
                { 
                    cout<<"-1"<<endl;
                    continue;
                }
                F(b[i],n);
            }
        }
        return 0;
    }

[Power OJ 2460_]: https://www.oj.swust.edu.cn/problem/show/2460