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 none and noun. We understand that problem is
somewhere further, in the second half. So we open this half in its middle and found turkey here - now we know that
the problem is somewhere between noun and 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 3-rd to 5-th element (5 and 11).
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 3
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
of 56132:
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 2 and
we C is the 56132 - result for which we are trying to find a suitable value of x.
Since 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
this value.
We provide Binary Search Task about this last variant - so you can practice the programming of this algorithm.