Если задано положительное целое число, выведите количество шагов, необходимых для поиска ввода с помощью двоичного поиска, начиная с 1.

Мы моделируем двоичный поиск целого числа, которое было задано в качестве входных данных, в котором смоделированный искатель может многократно угадывать целое число и сообщать, является ли оно слишком высоким, слишком низким или правильным. Стратегия нахождения целого числа следующая:

• Позвольте n быть целым числом, данным как входные данные, которые мы пытаемся найти.

• Начните с предположения 1. (Для каждого предположения увеличьте количество шагов (независимо от того, было ли оно правильным или нет), и немедленно остановите и выведите общее количество шагов, если предположение было правильным.)

• Повторяйте двойное предположение, пока оно не станет больше n (целевого числа). (Или, если это правильно, но это уже охватывается нашим правилом правильного угадывания, упомянутым выше.)

• Теперь установите верхнюю границу первой степени 2, которая больше, чем n (т.е. число, которое только что угадано), и установите нижнюю границу степени 2 непосредственно под ней.

• Повторно угадать среднее (округленное вниз) верхней границы и нижней границы. Если оно слишком высокое, установите его в качестве верхней границы. Если он слишком низкий, установите его в качестве нижней границы. Эта процедура гарантированно приведет к правильному предположению.

Вот пример для ввода n = 21:

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 24 -> 20 -> 22 -> 21
\__________________________/
   repeated doubling      \________________________/
                             repeated averaging

Поскольку это код-гольф , победит самый короткий код в байтах.

Вот все выходы от n = 1 до 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

И вот несколько больших тестовых случаев:

1234 -> 21
1337 -> 22
3808 -> 19
12345 -> 28
32768 -> 16
32769 -> 32
50000 -> 28

Japt, 13 12 байт

О, черт возьми, я некоторое время бил Джелли и Пита: D

¢a1 ªJ +1+¢l

Проверьте это онлайн!

Вот стратегия, которую я использую: пусть x будет входным целым числом, и пусть b будет двоичным представлением x . Правильный вывод равен 1 + длина b + последний индекс a 1 в b , минус 1, если этот индекс равен 0.

Желе, 18 15 10 9 байт

B>WU;BḄBL

Попробуйте онлайн! или проверьте маленькие тестовые случаи и большие тестовые случаи .

Фон

Пусть n - положительное целое число, а m - наименьшая степень 2, которая больше или равна или равна n .

• Удвоения фазы принимает один шаг для каждой цифры в двоичном представлении м .

• Возьмите двоичное представление n , удалите первую, самую значимую цифру (всегда 1 ) и все завершающие нули. Фаза усреднения принимает один шаг для каждой оставшейся цифры.

Чтобы избежать вычисления m , мы заметим, что если n <m , число двоичных цифр n ровно на единицу меньше числа двоичных цифр m .

Если мы заменим первую двоичную цифру n на 0 , перевернем результат, добавим исходные двоичные цифры и удалим все начальные нули, тогда произойдет следующее:

• Если n - степень 2 , все цифры первой (модифицированной) половины удаляются, оставляя только цифры исходного двоичного представления n = m .

• Если п является не степень 2 , цифра в первой половине , что соответствует наиболее значащей цифры никак не удаляются, компенсируя тем , что п имеет двоичную цифру меньше , чем т .

Как это устроено

B>WU;BḄBL  Main link. Input: n

B          Compute the binary representation of n.
 >W        Compare it with [n].
           n is positive, so it is not less than the first binary digit and the
           comparison yields zero. When comparing lists of different length, the
           elements in the longer list that do not have a pair remain untouched.
           Therefore, this will just zero out the first binary digit.
   U       Reverse the modified binary representation.
    ;B     Concatenate it with the unmodified binary representation of n.
      ḄB   Convert from binary to integer, and back to binary.
           This removes leading zeroes.
        L  Get the length of the resulting array.

ES6, 38 байт

x=>33-(g=Math.clz32)(x-1)+g(x&-x)-g(x)

Как на это указывают другие ответы, вы можете рассчитать количество шагов по позициям первого и последнего битов.

Количество шагов в фазе удвоения равно n=33-Math.clz32(x-1). Мы хотим, чтобы 2ⁿ ≥ x, но n=33-Math.clz32(x)дает нам 2ⁿ> x, поэтому мы вычитаем 1 из x для компенсации.

Количество шагов на этапе усреднения проще, это просто n=Math.clz32(x&-x)-Math.clz32(x). x&-xявляется удобным выражением, которое оценивается в младший бит x(как степень 2).

Pyth, 15 13 байт

h-y.ElQ/PPyQ2

Я обнаружил, что рассчитываемое число 1 + 2*ceil(log_2(x)) - [number of 2s in x's prime factorization, minus 1 if x is a power of 2 greater than 1].

Попробуй это здесь .

Юлия, 37 35 байт

n->endof(strip(bin(n-1)bin(n),'0'))

Спасибо @AlexA. за сохранение 2 байта!

Это следует из наблюдений из моего ответа желе , но по-разному относится к крайним случаям.

Если n> 1 , двоичное представление n - 1 имеет одну цифру меньше, чем цифра следующей степени 2 , что компенсируется отсутствием удаления первой цифры двоичного представления n .

Удаляя все нули с обеих сторон , мы также имеем дело с краевым случаем 1 .

Haskell, 82 байта

Это довольно простая реализация в Haskell:

f x=[j|j<-[1..],let g i|i<2=1|x>g(i-1)=2*g(i-1)|1<2=div(g(i-1)+g(i-2))2,g j==x]!!0

Меньше гольфа:

f x = head [ stepNum | stepNum <- [1..], step stepNum == x]
  where
    prevStep i = step (i-1)
    step i | i == 1         = 1
           | x > prevStep i = 2 * prevStep i
           | otherwise      = div (prevStep i + step (i-2)) 2