Home Problems Volumes Ranking Forum Help News Mess 13:37:38
Contents

Binary Search

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.

Dictionary example

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.

Number guessing game

See the description and the live example of the game and more detailed explanation are provided at dedicated page: Guessing Game

Sorted array example

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.

Math function example

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.