a209. 二分搜尋-終極密碼

Content

在玩終極密碼時，因為猜完可以得知猜測數字與正確答案之間的大小關係，因此二分搜尋法被視為可以快速找到正確答案的方法。

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

透過猜數字的範圍 $l$ 與 $r$ 取找到中間值 $\dfrac{l+r}{2}$（此題遇到無法整除時請無條件捨去）。
根據猜測的數字與正確答案的大小關係調整猜測數字的範圍 $l$ 與 $r$。
重複上述兩步驟直到猜中正確數字為止。

現在請你寫一支程式模擬用二分搜尋法進行猜密碼。

Input

輸入共一行，包含兩個數字 $n$ 、 $ans$。代表猜數字的範圍介於 $1 \sim n$ 之間（含），正確的答案為 $ans$。

Output

前面若干行輸出猜測的過程：

若猜測的數字 $k$ 太小，請輸出 $k$ is too small
若猜測的數字 $k$ 太大，請輸出 $k$ is too big
若猜測的數字 $k$為正確答案，請輸出 $k$ is correct

最後一行輸出總共猜測的次數。

Sample Input #1

100 43

Sample Output #1

50 is too big
25 is too small
37 is too small
43 is correct
4

Sample Input #2

10 10

Sample Output #2

5 is too small
8 is too small
9 is too small
10 is correct
4

測資資訊：

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

Hint ：

Tags:

binary search

出處:

[管理者： ktlai (K．我已霸榜．Tlai) ]

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