EOJ-自适应编程学习平台

第 1 行输入一个整数 n(1≤n≤1000)，第 2 行输入 n 个由一个空格分隔的 int 整数到一个数组中，第 3 行输入一个 int 整数 m。

对数组按升序排序，然后使用二分查找算法找出 m 是排序后数组中的第几个元素（这里计数从 1 开始）。找不到时，输出 “not found”。假设输入时数组中的各个元素值均不相同。

Note: 二分查找算法（Binary Search ）

m 与数组中间元素进行比较，确定是否相等，不是的话，则可能在前半部或后半部。如此反复，直至找到或者确定不在该数组中。

例如：1 3 5 7 53 355 3432 中找 3

3 与中间的那个元素 7 进行比较 : 1 3 5 7 53 355 3432 3

3 比 7 小，因此在前半部查找 : 1 3 5 3

Binary Search vs Sequential (Linear) Search

BS：比较次数最多 log₂n，必须是排好序的

SS: 比较次数最多 n，不一定是排好序的

参考资料：

http://en.wikipedia.org/wiki/Binary_search

例如：输入：

7

3432 1 3 355 7 53 5

3

输出：

2

又如：输入：

7

3432 1 3 355 7 53 5

-3

输出：

not found

第 1 行输入一个整数 n(1≤n≤1000)。

第 2 行输入 n 个由一个空格分隔的 int 整数到一个数组中。数组中的各个元素值均不相同。

第 3 行输入一个 int 整数 m。

在一行中输出 m 是排序后数组中的第几个元素（这里计数从 1 开始）。找不到时，输出 “not found”。