二分查找Ⅱ

题目描述:

给定一个包含n个关键字的有序（从小到大排列）数列，采用“二分查找算法”查找关键字x。要求输出：关键字的位置及进行比较的次数。

输入格式:

第一行一个整数n（n<=100,000）。

第二行包含n个从小到大有序的整数，各数之间用一个空格隔开。

第三行一个整数x。

 

输出格式:

两个整数，表示x所在的位置以及比较的总次数。

样例输入:

10
1 2 3 4 5 6 7 8 9 10
9

样例输出:

9 3

提示:

二分查找算法

因为整个序列已经有序（从小到大排），所以我们每次可以和区间的中间那个数去比较，比较的有三种情况：

1）相等，即找到；

2）如果要找的数比中间的那个数大，接下来在后半段继续找。

3）如果要找的数比中间的那个数小，接下来在前半段继续找。

样例解释：第1次和序列中的5比较，第2次和序列中的8比较，第3次和序列中的9比较。

时间限制: 1000ms
空间限制: 128MB

---

来源: 原创