Binary Search Algorithm

Let's discuss one of the search algorithms i.e. Binary Search Algorithm.

Binary Search Algorithm

The binary search algorithm is an effective and efficient technique for searching an item from the list of items sorted. 

For applying the binary search algorithm, the only limitation is that the array or list of the elements must be sorted. 

In this algorithm, the sorted array or list is searched by frequently fragmenting the search interval in half. 

Firstly, it starts with an interval covering the entire list. 

If the search key’s value is less than the item in the center of the interval, then narrow the interval to the lower half. 

Else narrow it to the upper. 

Again and again inspect, until the value is identified or the interval is vacant. 

The example of a binary search algorithm is demonstrated through the figure described below:

Suppose there is an array, array = {1,5,7,8,13,19,20,23,29}. 

Now we need to search for the location of item 23.

Binary Search Algorithm Explained

Let us consider low is the lowest index position, mid is the center index position and high is the possible highest index position i.e. 0, 4, and 8 respectively at first.

In First Step:

low = 0, mid = (low + high)/2 = (0 + 8)/2 = 4, high = 8

a [mid] = a [4] = 13 since 13 is less than 23 so,

In Second Step:

low = mid + 1 = 4 + 1 = 5, high = 8, mid = 13/2 = 6

a [mid] = a [6] = 20 since 20 is also less than 23 so again,

In Third Step:

low = mid + 1 = 6 + 1 = 7, high = 8, mid = 15/2 = 7 since 7.5 is not considered

           a [mid] = a [7] = 23 i.e. a searched item of an array. The index of that item is 7.

In the context of a binary search algorithm, at first, a condition is set that checks whether the given array has some value or not. 

If not, then integer -1 is returned otherwise the first value to be searched is compared with the middle value. 

If the value matches while comparing, then the index number of that particular array is returned otherwise that array is fragmented into two halves. 

Before fragmenting the array, the value is properly checked whether it is smaller than the middle value or greater. 

As the array is sorted, either the value is compared to the array having a starting index number greater than the index number of the middle value or to the array having the last index number smaller than the index number of middle values. 

This process occurs repeatedly until and unless the searched value is identified or the lowest index number is smaller than the highest index number.