CCF NOI1115 找数

问题链接：CCF NOI1115 找数。

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

给一个长度为n的单调增的正整数序列，即序列中每一个数都比前一个数大。有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？

输入

给一个长度为n的单调增的正整数序列，即序列中每一个数都比前一个数大。有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？

输出

输出共m行，表示序列中最后一个小于等于x的数是多少。假如没有输出-1。

样例输入

5 3
1 2 3 4 6
5
1
3
样例输出

数据范围限制

1<=n,m<=100000,序列中的元素及x都不超过10^6。

提示

问题分析

这是一个查找问题，二分法是常用的。

输入的数是有序的，并且是从小到大。

程序说明

函数find()是一个典型的二分查找程序。

要点详解

使用宏定义可以使得代码可阅读性增强。
要根据输入数的值范围选用类型。
从重用性角度考虑，编写C语言程序时应该尽量把一些功能封装到函数中。

参考链接：（略）。

100分通过的C语言程序：

#include <stdio.h>

#define N 100000
int a[N];

int find(int left, int right, int x)
{
    int mid;

    while(left <= right) {
        mid = (left + right) / 2;

        if(a[mid] == x)
            return a[mid];
        else if(a[mid] < x)
            left = mid + 1;
        else // if(a[mid] > x
            right = mid - 1;
    }

    return a[right];
}

int main(void)
{
    int n, m, x, i;

    while(scanf("%d%d", &n, &m) != EOF) {
        a[0] = -1;
        for(i=1; i<=n; i++)
            scanf("%d", &a[i]);

        for(i=1; i<=m; i++) {
            scanf("%d", &x);

            printf("%d
", find(1, n, x));
        }
    }

    return 0;
}