1659_二分查找II

二分查找又叫折半查找。它采用的是"分治策略"。

给出非降序排列的M个整数，查找是否存在某个整数，如果存在，则输出其位置。

定义向量数据结构如下：

#define  MAX_SIZE  5000000

/// 简陋定义方式

int mydata[ MAX_SIZE ];   /// 向量元素存放的数组

int _size;   /// 向量元素的实际个数

第一行是一个整数 M ( 0 < M ≤ 5000000 ) 表示整数的个数。

接下来是M个整数，每个整数之间用一个空格分隔。

接下来一行是一个整数N，表示要查找的关键字个数。

接下来N个整数，表示要查找的关键字key。每个key之间一个空格分隔。

对每个要查找的key，输出一行结果：如果找到，输出key在这M个整数的秩，位置从0开始编号。

如果有多个相同的向量元素，返回最后一个的秩。

如果找不到，则输出这个元素如果插入到这个有序序列时，为保持序列依然有序，所应该插入的位置，即 秩。

10
1 2 4 6 7 8 9 20 20 85
4
1 5 20 99

0
3
8
10

注：元素5不存在数列中，若将其插入数列，应该在下标3的位置，所以返回3。

元素99同理。