Biorąc pod uwagę dodatnią liczbę całkowitą, wypisz liczbę kroków potrzebnych do znalezienia danych wejściowych poprzez wyszukiwanie binarne od 1.
Symulujemy binarne wyszukiwanie liczby całkowitej podanej jako dane wejściowe, w której symulowany wyszukiwarka może wielokrotnie zgadywać liczbę całkowitą i otrzymywać informację, czy jest ona za wysoka, za niska lub poprawna. Strategia znajdowania liczby całkowitej jest następująca:
Niech n będzie liczbą całkowitą podaną jako dane wejściowe, które próbujemy znaleźć.
Zacznij od zgadywania 1. (Dla każdego zgadnięcia zwiększ liczbę kroków (niezależnie od tego, czy było poprawne, czy nie)) i natychmiast zatrzymaj i wyślij całkowitą liczbę kroków, jeśli zgadnięcie było poprawne.)
Dwukrotnie zgadnij, aż zgadnięcie będzie większe niż n (liczba docelowa). (Lub jeśli jest to poprawne, ale jest to już objęte naszą regułą zgadywania, o której mowa powyżej.)
Teraz ustaw górną granicę pierwszej potęgi 2, która jest większa niż n (tj. Właśnie odgadnięta liczba), i ustaw dolną granicę potęgi 2 bezpośrednio pod nią.
Wielokrotnie zgadnij średnią (zaokrągloną w dół) górnej granicy i dolnej granicy. Jeśli jest za wysoko, ustaw go jako górną granicę. Jeśli jest za niski, ustaw go jako dolną granicę. Ta procedura gwarantuje, że ostatecznie spowoduje prawidłowe zgadnięcie.
Oto przykład wprowadzenia n = 21:
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 24 -> 20 -> 22 -> 21
\__________________________/
repeated doubling \________________________/
repeated averaging
Ponieważ jest to code-golf , wygra najkrótszy kod w bajtach.
Oto wszystkie dane wyjściowe od n = 1 do n = 100:
1
2
4
3
6
5
6
4
8
7
8
6
8
7
8
5
10
9
10
8
10
9
10
7
10
9
10
8
10
9
10
6
12
11
12
10
12
11
12
9
12
11
12
10
12
11
12
8
12
11
12
10
12
11
12
9
12
11
12
10
12
11
12
7
14
13
14
12
14
13
14
11
14
13
14
12
14
13
14
10
14
13
14
12
14
13
14
11
14
13
14
12
14
13
14
9
14
13
14
12
A oto kilka większych przypadków testowych:
1234 -> 21
1337 -> 22
3808 -> 19
12345 -> 28
32768 -> 16
32769 -> 32
50000 -> 28