**Binary Search**

Binary Search method works only for sorted list.

This method of searching is more efficient as compared to linier search method. Because we does not have to compare the search element with all the elements in the list until the element is found.

The binary search method of searching an element works as follow:

Suppose we want to search an element **X** from the list of N element.

Determine the Lower and Upper limit of the list by assigning Lower index of the list to LOW and Upper Index of the list to HIGH. Now calculate the MIDDLE position using following equation:

MIDDLE = (LOW + HIGH)/2

After finding the MIDDLE index from the list we compare the value of the MIDDLE element with X.

If the value of the middle element is greater then X then it will exist in the lower interval of the list. So we change the value of HIGH index by MIDDLE – 1.

If the value of the middle element is smaller then X then it will exist in the upper interval of the list. So we change the value of LOW index by MIDDLE + 1

This process is repeated until entire list is searched or the element is found.

Consider following example:

LOW |
MIDDLE |
HIGH |
|||||||

0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |

23 |
45 |
67 |
89 |
123 |
189 |
210 |
235 |
345 |
545 |

Suppose we want to find the element** X=189** in the above list.

First,

**LOW = 0, HIGH = 9**

**MIDDLE = (LOW + HIGH)/2
= (0+9)/2
= 4.5 = 4**

Here the value of MIDDLE element is **123** which is less then **189** so the element is in the upper interval of the list. Now change the value of **LOW = MIDDLE + 1 = 4 +1 =5**.

LOW |
MIDDLE |
HIGH |
||

5 |
6 |
7 |
8 |
9 |

189 |
210 |
235 |
345 |
545 |

**Now,
LOW = 5, HIGH = 9
Middle=(LOW+HIGH)/2 = (5+9)/2 = 14/2 = 7**

Here the value of MIDDLE element is

**235**which is greater then

**189.**So the element is in the lower interval of the list. Now change the value of

**HIGH = MIDDLE - 1 = 7 - 1 =6**.

**Now,
LOW = 5, HIGH = 6
Middle=(LOW+HIGH)/2 = (5+6)/2 = 11/2 = 5.5 = 5**

Here the value of MIDDLE element is

**189**which is equal to

**189.**So the element is found in the list.