1009: 手把手教你写二分

题目描述

二分查找，是用来在一个有序数组中查找某一元素的算法。以在一个升序数组中查找一个数为例，它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需要到右侧去找就好了；如果中间元素大于所查找的值，同理，右侧的只会更大而不会有所查找的元素，所以只需要到左侧去找。

身为一个不靠谱助教，本来也很想手把手教大家写二分，但是助教作业也写不完了！！！所以，更详细的内容请看翁阿姨程序设计教材85页。

给定一个长度为$n$的升序序列$a_1,\ldots a_n$。

给定$m$次询问，第$j$次询问给定$b_j$，请求出$a$序列中第一个大于等于$b_j$的数字，也就是{$a_i|1\leq i \leq n，a_i\geq b_j$}这个集合中的最小值，如果不存在这样一个数字，请输出-1。

输入格式

第一行有两个整数，分别表示$n,m$.

第二行有$n$个整数，分别表示$a_1,\ldots,a_n$.

第三行有$m$个整数，分别表示$b_1,\ldots,b_m$.

输出格式

一共有$m$行，每行一个数字表示$a$序列中第一个大于等于$b_j$的数字。

样例输入

样例输入 1

5 5 2 4 6 8 10 4 20 9 1 5

样例输入 2

5 5 6 10 20 70 100 90 60 1000 1 9

样例输出

样例输出 1

4 -1 10 2 6

样例输出 2

100 70 -1 6 10

数据范围

$n,m \leq 10^5$.

$0<a_i,b_i \leq 10^5$.

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！