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.

Download Projects


Download Programs