Ace The 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.

Binary search works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.

Binary Search

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.

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)-0

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.

Implementation of binary search in C++

kvvik2020

Beyond Sorted Array Binary Search

Binary search obviously works on searching for elements in a sorted array. But if you think about the reason why it works is because the array itself is monotonic ( either increasing or decreasing ). So, if you are a particular position, you can make a definite call whether the answer lies in the left part of the position or the right part of it.

Similar thing can be done with monotonic functions ( monotonically increasing or decreasing ) as well.
Lets say we have f(x) which increases when x increases.

So, given a problem of finding x so that f(x) = p, I can do a binary search for x.

At any instance,
1. if f(current_position) > p, then I will search for values lower than current_position.
2. if f(current_position) < p, then I will search for values higher than current_position
3. if f(current_position) = p, then I have found my answer.