《信息学奥赛一本通》分治算法 找数 例题

【描述】

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

【输入】

第一行两个整数n，m。 接下来一行n个数，表示这个序列。 接下来m行每行一个数，表示一个询问。

【输出】

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

【样例输入】

5 3 1 2 3 4 6 5 1 3

【样例输出】

4 1 3

【分析】

用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]