Tutorials

# Binary Search

Linear search is bit slow as it needs to compare each element from beginning to end to find the desired element.

So binary search is extremely efficient algorithm as it searches required item in minimum possible comparisions.

Binary search is possible only on sorted array.

After sorting the array, binary search is performed as below:

1. First we need to calculate the middle index of the array.
2. Compare the element at middle index with item to be searched.
3. If the middle element is the required element then search is successful.
4. If middle element is greater than desired item then search only the first half of the array.
5. If it middle element is less than desired item then search only the second half of the array.
6. Step 1 to 5 is repeated on the part of array which is next to be searched and will be repeated until desired element is found.

In binary search every time the number of element that needs to be searched is reduced by almost half thus making it more efficient than linear search.

See the below diagram to understand the binary search work in detail.

### Example on binary search

Suppose we are given a sorted array as shown below:

In the above array we need to search 78.

Step I:

first index = 0, last index = 6

mid = (first index + last index)/2= (0+6)/2 = 6/2 = 3

We have marked element at index 3 with circle. This is the mid value.

Step II:

a[mid] < item to be searched,

first index = mid + 1 = 3 + 1 = 4

Now second part of the array will be searched as shown below:

Step III:

first index = 4, last index = 6

mid = (first index + last index)/2= (4+6)/2 = 10/2 = 5

Step IV:

a[mid]=item to be searched.

Binary search completes.