a249. 二分搜尋法-陣列中搜尋

Content

二分搜尋法最常運用的情境，是在有序（從小排到大或從大排到小）的數列中，找到特定數值所在的位置。

二分搜尋法的實作方法如下：

透過猜數字的範圍 $l$ 與 $r$ 取找到中間值 $m = \dfrac{l+r}{2}$（此題遇到無法整除時請無條件進位）。
根據猜測的位置 $m$ 取得 $A[m]$ ，並透過 $A[m]$ 與尋找的值之間的大小關係，調整猜測數字的範圍 $l$ 與 $r$。
重複上述兩步驟直到猜中正確位置或確定數字不存在陣列中為止。

Input

第一行輸入一個整數 $n$， $n \le 10^4$

第二行輸入 $n$ 個從小排到大的數字 $A_1, A_2, \dots, A_n$，所有的 $A_i$ 不超過 $10^7$，而且不會有標準的數字。

第三行輸入要尋找的數字 $k$。

Output

第一行輸出 $k$ 在陣列中的位置（從 $1$ 開始計算），如果找不到請輸出 $0$。

第二行輸出詢問的次數。

Sample Input #1

10
1 3 5 7 8 9 20 21 35 100
35

Sample Output #1

9
2

Sample Input #2

10
1 3 5 7 8 9 20 21 35 100
10

Sample Output #2

0
4

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M

Hint ：

Tags:

binary search

出處:

[管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」