python/TangDou/XiTi/1305.cpp

#include <bits/stdc++.h>

using namespace std;

int n, m, a[10000] = {-1};

int main() {
    //输入+输出重定向
    freopen("../1305.txt", "r", stdin);
    //录入数据
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //m个询问
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        int left = 1, right = n, mid;
        /*
        用left表示序列的左边界，用right表示序列的右边界，[left，right]组成序列。
        一开始left=1，right=n。序列已经按照升序排好，保证了二分的有序性。

        二分法
        二分的步骤：
        1.去序列区间的中间值mid=(left+right)/2；
        2.判断mid与x的关系，如果a[mid]>x，所以区间[mid,right]直接排除，修改right=mid-1；如果a[mid]<=x，所以区间[left，mid]直接排除，修改right=mid+1；
        3.重复执行二分操作直到left>right。最终循环结束时一定是left=right+1，所以最后的结果为right指向的值。
        4.如果在序列中找不到合适的位置，或者说是在最前面添加上的话，那么right=0,需要将a[0]设置为-1.
         */
        while (left <= right) { //注意是小于等于
            mid = (left + right) / 2; //取中间值
            if (a[mid] <= x) {
                left = mid + 1; //在右边，则left修改为mid+1
            } else { //在左边，则right修改为mid-1
                right = mid - 1;
            }
        }
        //cout << "left=" << left << ",right=" << right << endl;
        cout << a[right] << endl;
    }

//关闭文件
    fclose(stdin);
    return 0;
}