In computer science the Binary Search is the name of the simple and efficient algorithm for finding a position where monotonic function reaches the given value. ("Monotonic" means that its values steadily grow with growing argument). Extensive explanation of theory could be found in wikipedia on Binary Search. Below few ordinary usage examples are provided with sample calculations.
Usual application is the search through sorted array as in dictionary by alphabet. In this case argument of a function is the page number (or word number) and the value - the word itself (first word on the page for example).
For example, if we search for word
problem we open dictionary at the middle and see here words like
noun. We understand that
somewhere further, in the second half. So we open this half in its middle and found
turkey here - now we know that
problem is somewhere between
turkey, i.e. at third quarter of the dictionary - we open it in the
middle... and proceed, shrinking range to search about twice times with each step, until we found a page we want.
See the description and the live example of the game and more detailed explanation are provided at dedicated page: Guessing Game
Monotonic function can be represented by sorted array. Suppose we have sorted array with the following numbers:
2 3 5 7 11 13 17 19 23 29
And we want to find if number
9 is included in it. Since size is
10, we peek in the middle for
5-th element. It
appears to be
11, so we should search only in the first half. We peek in the middle of the half and we find element
5 here. Our number should be after it, so we are searching in the range from
5-th element (
Peeking in the middle we find
7 here. We should search somewhere after it. However, now the range is reduced to only
two elements, one of which is less than and other greater than the value which is searched for. So in only
operations we discover that the element in question is absent from array.
Quite important application of Binary Search is for solving equations. Of course it is important that equation
is represented by or could be converted to monotonic function. For example, suppose we want to find the square root
Square root could be found by specific method (for example Heron's), however we can use approach involving the Binary Search. Let us write the equation:
we want: x = sqrt(56132) that means: x * x = 56132
So we want to solve equation
f(x) = C where
f(x) is the function of raising the value to the power of
C is the
56132 - result for which we are trying to find a suitable value of
f(x) = x*x is monotonous function, we can use the Binary Search.
At first let us define suitable range for search. Obviously
f(0) = 0 - so let
x = 0 be the left end of
the range. Meanwhile
f(1000) = 1000000 which is much greater than
56132 and hence could be the
other (right) end.
We than calculate:
for segment 0 ... 1000: f(0) = 0, f(1000) = 1000000 xMiddle = (0 + 1000) / 2 = 500 f(500) = 250000 56132 is less than 250000, so take first half for segment 0 ... 500: f(0) = 0, f(500) = 250000 xMiddle = (0 + 500) / 2 = 250 f(250) = 62500 56132 is less than 62500, so take the first half for segment 0 ... 250: f(0) = 0, f(250) = 62500 xMiddle = (0 + 250) / 2 = 125 f(125) = 15625 56132 is greater than 15625, so take the second half for segment 125 ... 250: f(125) = 15625, f(250) = 62500 xMiddle = (125 + 250) / 2 = 187 f(187) = 34969 56132 is greater than 34969, so take the second half for segment 187 ... 250: ...
From now try to proceed on your own and make sure that the root is found precisely enough and fast enough.
These iterations should be performed until segment size (i.e. search range length) becomes smaller than acceptable
error. For example, if we want to find
x with precision of
e = 0.001, we can stop when segment size is less than
We provide Binary Search Task about this last variant - so you can practice the programming of this algorithm.