SSOJ1368大理石在哪儿
3040+
作者：crxis 发布：2017-10-05 分类：二分
题目大意：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。
程序实现
递归的二分查找
二分的非递归写法
