Binary Search Algorithm

In this class, we will try to understand the Binary Search Algorithm.

In our previous class, we have already discussed the linear search algorithm.

The design of the Binary Search Algorithm is based on the divide and conquer algorithm design technique.

The array of elements in the binary search algorithm is in sorted order.

The binary search algorithm will work only if the array elements are in the sorted order.

Before understanding the Binary Search Algorithm, we will understand the working mechanism.

To understand the Binary Search Algorithm working mechanism, we will consider the array of elements as shown below.

Assume that we are searching for 3.

On the above array, we will find the index of the mid element.

To find the mid element, we will consider the following formula.

mid = Floor( ( Low + High )/2)

In our case, the index of the mid-element is 4.

Now we will compare the element in the mid index with the element to be searched.

We will compare 5 with 3.

They are not equal.

Now we will check whether the element to be searched is less than the mid element or greater than the mid element.

If the element to be searched is less, we will consider only the elements to the left of the mid-element.

If the element to be searched is greater, we will consider only the elements to the right of the mid-element.

We will now find the mid element on that part of the array.

In our case, the element to be searched is less, so we will consider only the left part of the array.

Now the mid-element index is 1. The element at index 1 is 2.

The mid element is not equal to the element to be searched.

The element to be searched is greater than the mid-element.

So the right part of the mid-element is considered.

The right part of the mid-element has elements 3 and 4.

Now we will find the mid-element.

The mid-element is at index 2.

The element to be searched is equal to the element in the mid-element whose index is returned.

The algorithm for the Binary Search is shown below.

The above algorithm is recursive.

If low > high, then the element is not found.

The else-if will get executed based on the element to be searched.