当前位置:首页 > 二分 > 正文
SSOJ1368大理石在哪儿
594+

题目大意:n个石头上,有n个各不相同的数字,现有q个询问,问某个数字的石头是否存在,如果存在,那么他是第几个(第几小)?

题目描述

现在有N个大理石,每个大理石上写了一个非负整数,首先要把各个数字由小到大排序,然后回答Q个问题,每个问题问是否有一个大理石写着某个整数x,如果是,还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。

输入

第一行:N Q

第二行:N个数,每个数空格隔开。

第三行:Q个数,每个数空格隔开

输出

输出,每个询问输出一行

如,询问的数字是a

如果a存在,则输出

a found at 位置

如果a不存在,则输出

a not found

特别说明:不存在两个相等数

样例输入

5 2
1 5 3 2 6
4 3

样例输出

4 not found
3 found at 3

提示

Q<100000

N<100000

解题思路

排序后,对于每个询问,找一下是否存在对应的数字,如果存在输出它排序后的位置,否则输出不存在。问题是怎么着?逐个查找的话,时间复杂度是O(n*q),对于10万的数据是会超时的。因此,不能直接遍历查找,而应该利用排序后的单调递增性质,二分查找。先找中间那个,如果中间那个太大,就找后半部分,如果太小,就找前半部分,如果相等直接返回位置,如果最后找着找着,区间不存在了,说明找不到返回0。

程序实现

递归的二分查找

二分的非递归写法

更多

About

坚决不Copy代码!

本文标签:,,,,

SSOJ1368大理石在哪儿:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter