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.

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.