Number of steps for a binary search

Question

Given an input of a positive integer, output the number of steps it takes to find the input via a binary search starting at 1.

We are simulating a binary search for the integer that was given as input, in which the simulated searcher can repeatedly guess an integer and be told whether it is too high, too low, or correct. The strategy for finding the integer is as follows:

• Let n be the integer given as input that we are trying to find.

• Start with a guess of 1. (For every guess, increment the number of steps (regardless of whether it was correct or not), and immediately stop and output the total number of steps if the guess was correct.)

• Double the guess repeatedly until the guess is greater than n (the target number). (Or if it is correct, but that's already covered by our correct-guess rule mentioned above.)

• Now, set an upper bound of the first power of 2 that's greater than n (i.e. the number that was just guessed), and set a lower bound of the power of 2 directly below it.

• Repeatedly guess the average (rounded down) of the upper bound and the lower bound. If it is too high, set it as the upper bound. If it is too low, set it as the lower bound. This procedure is guaranteed to eventually result in a correct guess.

Here's an example, for the input of n=21:

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

Since this is code-golf, the shortest code in bytes will win.

Here are all outputs from n=1 to 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

And here are some larger test cases:

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

Answer 1

Japt, 13 12 bytes

Oh my gosh I was beating both Jelly and Pyth for a time :D

¢a1 ªJ +1+¢l

Test it online!

Here's the strategy I use: let x be the input integer, and let b be x's binary representation. The correct output is 1 + the length of b + the last index of a 1 in b, minus 1 if this index is 0.

Answer 2

Jelly, 18 15 10 9 bytes

B>WU;BḄBL

Try it online! or verify the small test cases and large test cases.

Background

Let n be a positive integer and m the smallest power of 2 that is greater or equal than or equal to n.

• The doubling phase takes one step for each digit in the binary representation of m.

• Take the binary representation of n, remove the first, most significant digit (always 1) and all trailing zeroes. The averaging phase takes one step for each remaining digit.

To avoid calculating m, we observe that, if n < m, the number of binary digits of n is exactly one less than the number of binary digits of m.

If we replace the first binary digit of n with a 0, reverse the result, append the original binary digits and remove all leading zeroes, then following happens:

• If n is a power of 2, all digits of the first (modified) half get removed, leaving only the digits of the original binary representation of n = m.

• If n is not a power of 2, the digit in the first half that corresponds to the most significant digit does not get removed, compensating for the fact that n has a binary digit less than m.

How it works

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.

Answer 3

ES6, 38 bytes

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

As alluded to by other answers, you can calculate the number of steps from the positions of the first and last bits.

The number of steps in the doubling phase is n=33-Math.clz32(x-1). We want 2ⁿ ≥ x but n=33-Math.clz32(x) gives us 2ⁿ > x so we subtract 1 from x to compensate.

The number of steps in the averaging phase is easier, it's simply n=Math.clz32(x&-x)-Math.clz32(x). x&-x is a handy expression that evaluates to the lowest bit of x (as a power of 2).

Answer 4

Pyth, 15 13 bytes

h-y.ElQ/PPyQ2

I have found that the number to be calculated is 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].

Try it here.

Answer 5

Julia, 37 35 bytes

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

Thanks to @AlexA. for saving 2 bytes!

This follows the observations from my Jelly answer, but deals differently with the edge cases.

If n > 1, the binary representation of n - 1 has one digit less than the one of the next power of 2, which is compensated by not removing the first digit of the binary representation of n.

By removing all zeroes from both sides, we deal with the edge case 1 as well.

Answer 6

Haskell, 82 bytes

This is a pretty straightforward implementation in 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

Less golfed:

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