Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!