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.