- divede your problem into one or more pieces
- conquer the pieces by solving them recursively
- combine the pieces in some way
Strategy: Keep eliminating half of all numbers
Binary logarithmFrom Wikipedia, the free encyclopedia
Graph of log2 x as a function of a positive real number xIn mathematics, the binary logarithm (log2 n) is the power to which the number 2 must be raised to obtain the value n. That is, for any real number x,
For example, the binary logarithm of 1 is 0, the binary logarithm of 2 is 1, the binary logarithm of 4 is 2, and the binary logarithm of 32 is 5.
The binary logarithm is the logarithm to the base 2. The binary logarithm function is the inverse function of the power of two function. As well as log2, alternative notations for the binary logarithm include lg, ld, lb, and (with a prior notation that the default base is 2) log.
Binary logarithms are included in the standard C mathematical functions and other mathematical software packages. The integer part of a binary logarithm can be found using the find first set operation on an integer value, or by looking up the exponent of a floating point value. The fractional part of the logarithm can be calculated efficiently using a recursive algorithm.