Dada a entrada de um número inteiro positivo, imprima o número de etapas necessárias para encontrar a entrada por meio de uma pesquisa binária iniciando em 1.

Estamos simulando uma pesquisa binária do número inteiro que foi dado como entrada, na qual o pesquisador simulado pode adivinhar repetidamente um número inteiro e saber se ele é muito alto, muito baixo ou correto. A estratégia para encontrar o número inteiro é a seguinte:

• Seja n o número inteiro dado como entrada que estamos tentando encontrar.

• Comece com um palpite de 1. (Para cada palpite, aumente o número de etapas (independentemente de estar ou não correto) e pare imediatamente e emita o número total de etapas, se a palpite estiver correta.

• Duplique o palpite repetidamente até que o palpite seja maior que n (o número de destino). (Ou se estiver correto, mas isso já está coberto pela nossa regra de palpite correta mencionada acima.)

• Agora, defina um limite superior da primeira potência de 2 maior que n (ou seja, o número que foi adivinhado) e defina um limite inferior da potência de 2 diretamente abaixo dela.

• Adivinhe repetidamente a média (arredondada para baixo) do limite superior e do limite inferior. Se estiver muito alto, defina-o como o limite superior. Se estiver muito baixo, defina-o como o limite inferior. Este procedimento é garantido para eventualmente resultar em uma estimativa correta.

Aqui está um exemplo, para a entrada de n = 21:

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

Como esse é o código-golfe , o código mais curto em bytes será vencedor.

Aqui estão todas as saídas de n = 1 para 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

E aqui estão alguns casos de teste maiores:

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

Japonês, 13 12 bytes

Oh meu Deus, eu estava batendo Jelly e Pyth por um tempo: D

¢a1 ªJ +1+¢l

Teste online!

Aqui está o uso estratégia que eu: que x é a entrada inteiro, e deixe b seja x 's binária representação. A saída correta é 1 + o comprimento de b + o último índice de a 1 em b , menos 1 se esse índice for 0.

Geléia, 18 15 10 9 bytes

B>WU;BḄBL

Experimente online! ou verifique os casos de teste pequenos e grandes .

fundo

Seja n um número inteiro positivo e m a menor potência de 2 maior ou igual a ou igual a n .

• A fase de duplicação dá um passo para cada dígito na representação binária de m .

• Pegue a representação binária de n , remova o primeiro dígito mais significativo (sempre 1 ) e todos os zeros à direita. A fase de média dá um passo para cada dígito restante.

Para evitar o cálculo de m , observamos que, se n <m , o número de dígitos binários de n é exatamente um a menos que o número de dígitos binários de m .

Se substituirmos o primeiro dígito binário de n por 0 , inverta o resultado, acrescente os dígitos binários originais e remova todos os zeros à esquerda, e acontece o seguinte:

• Se n for uma potência de 2 , todos os dígitos da primeira metade (modificada) serão removidos, deixando apenas os dígitos da representação binária original de n = m .

• Se n não for uma potência de 2 , o dígito na primeira metade que corresponder ao dígito mais significativo não será removido, compensando o fato de que n tem um dígito binário menor que m .

Como funciona

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 bytes

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

Conforme mencionado por outras respostas, você pode calcular o número de etapas a partir das posições do primeiro e do último bits.

O número de etapas na fase de duplicação é n=33-Math.clz32(x-1). Queremos 2ⁿ ≥ x, mas n=33-Math.clz32(x)nos dá 2ⁿ> x, então subtraímos 1 de x para compensar.

O número de etapas na fase média é mais fácil, é simples n=Math.clz32(x&-x)-Math.clz32(x). x&-xé uma expressão útil que avalia o bit mais baixo de x(como uma potência de 2).

Pitão, 15 13 bytes

h-y.ElQ/PPyQ2

Eu descobri que o número a ser calculado é 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].

Experimente aqui .

Julia, 37 35 bytes

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

Graças a @AlexA. para economizar 2 bytes!

Isto segue as observações da minha resposta Jelly , mas lida de maneira diferente com os casos extremos.

Se n> 1 , a representação binária de n - 1 tem um dígito a menos que o da próxima potência de 2 , que é compensada por não remover o primeiro dígito da representação binária de n .

Removendo todos os zeros de ambos os lados , lidamos também com o caso 1 da aresta .

Haskell, 82 bytes

Esta é uma implementação bastante direta no 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

Menos golfe:

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