Skip to content

14266: 【原4266】手把手教你写二分

题目

题目描述

author: Guo Linsong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4266

Description

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

身为一个不靠谱助教,本来也很想手把手教大家写二分,但是助教作业也写不完了!!!所以,更详细的内容请看翁阿姨程序设计教材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。

Input Format

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

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

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

$n,m \leq 10^5$.

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

Output Format

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

Sample Input 1

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

Sample Output 1

4
-1
10
2
6

Sample Input 2

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

Sample Output 2

100
70
-1
6
10

Oops! 本题目还没有解答!

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

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

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