The number of times binary search runs increases logarithmically with the number of elements it has to search. This is the opposite of an exponential increase. For example, the algorithm must run a maximum of 2 times to search 4 items, 3 times to search 8 items, and only 5 times to search 32 items
BINERY SEARCH
Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.
logarithmic
We will shortly encounter algorithms that run in time proportional to log N for some suitable defined N. The base-10 logarithm of a value is the exponent to which 10 must be raised to produce the value. It is written as 'log10', and usually abbreviated as just 'log'. Thus
log10 1000 is 3
log10 90 is slightly less than 2
log10 1 is 0
In algorithms, we commonly deal with the base-2 logarithm, defined similarly, written ‘log2’, and abbreviated as ‘lg’.
lg 1024 is 10
lg 9 is slightly more than 3
lg 1 is 0
Algorithms for which the running time is logarithmic are those where processing discards a large quantity of values in each iterations. The binary search algorithm you encountered a few weeks back (in the “guess a number” game) is an example. In each iteration, the algorithm discards half the possible values for the searched-for number. We will see further applications of logarithmic behavior when we work with trees in subsequent activities.
Top comments (0)