/ Algorithms

Algorithms And Logarithms

Binary Search Algorithm

Maximum number of guesses for a targeted value in an array of length n is $$log_2{n}$$

$$log_2{64}=6$$

$$2^6=64$$

$$2^0=1$$

$$log_{base}{x}=y$$

$$base^y=x$$

$$base^0=1$$

A value in an array of 64 elements can be found in 7 guesses (i.e. 32,16,8,4,2,1 + 1).

128 elements - 8 guesses.

256 elements - 9 guesses.

512 elements - 10 guesses.

1024 elements - 11 guesses.

2048 elements - 12 guesses.

4096 elements - 12 guesses.

1,048,576 elements - 21 guesses. (i.e. - $$(log_2{1,048,576}) + 1 = 20 + 1 =21$$)