Binary Search

Binary search is the most popular and efficient searching algorithm having an average time complexity of O(log N). Like linear search, we use it to find a particular item in the list.

What is binary search?

Binary search begins by comparing the middle element of the list with the target element. If the target value matches the middle element, its position in the list is returned. If it does not match, the list is divided into two halves.

The first half consists of the first element to middle element whereas the second half consists of the element next to the middle element to the last element.  If target value is greater than middle element, first half is discarded. Then same steps follow on until we find the target value’s position.

Note that most important point is list should be sorted. So to sort the list, check out these sorting algorithms and decide which fits your case best.

Well, this algorithm is not something new ninja technique we are not familiar with. You may have come across one of those card tricks where your friend perfectly guesses your selected card. And you were like, “Isn’t this magic or something😮”. To tell you the truth, it is one of the applications of binary search algorithm. Same goes for the guessing game.

Time and Space Complexities :

• Best Time Complexity: O(1)
• Average Time Complexity: O(log n)
• Worst Time Complexity:  O(log n)
• Best Space Complexity: O(1)

Pseudo code for binary search:

BinarySearch(array, target):
{
    left = lowestBound(array)
    right = highestBound(array)

    WHILE (left <= right)
    {
        middle = (left + right) / 2
        if(target = array[middle])
            RETURN middle
        else if(target < array[middle])
           right = middle - 1
        else
           left = middle + 1
    }
    RETURN -1
}

Check out this cool animation here to visualize binary search.

Example:

Consider the following list of 5 numbers: 21, 22, 23, 24, 25. We need to find whether number 25 is present in the list or not.

Applying binary search, the calculated bounds will be: left = 0, right = 4 & middle = (0 + 4)/2 = 2

While left bound < right bound, we go on dividing the list into 2 halves. If target element is equal to element at middle index, we find the position of target element. Else if it is less than element at middle index, decrement the right bound by 1. Again we calculate middle value by taking new right and left bounds. Follow these steps till we find the position of target element.

Let’s Code

To code in any language other than Python,  Click here 

Python program to implement linear search: