Binary search - The most loved one by interviewer!

Let’s discuss the intuition behind binary search. Have you ever looked for a page number in a book? If so, you probably used the technique of starting at the middle and slowly moving back or forth until you found the desired page. In binary search (BS), the place we search is called the search space, and the middle element of the search space is called the “mid” of the algorithm. For example, in a book with 100 pages, the search space is the pages in the book, and the mid would be page 50.

People often think that binary search can only be implemented on a sorted array, but that’s not the case. BS can be used on any increasing or decreasing amount, and it can also be used on a sequence that goes from false to true. In these cases, we can use BS to find our solution.

Now let’s talk about the implementation of BS. The most exciting part is actually implementing it! For instance, let’s take a sorted array of numbers:

num = [12, 23, 45, 89, 90, 90], n=6

We define some parameters, such as a lower bound, upper bound, and middle element, which are commonly represented as l, r, and mid. The algorithm works by discarding the half of the array that doesn’t contain the desired value, just like when we find a page in a book.

We first calculate the mid of the array and compare it with the target value. Based on the comparison, we decide whether the answer will fall on the left or right side of the mid. If we find the element on the left side, we discard the right side completely and move forward.

Here is the implementation of the algorithm:

int binary_search(int num[], int l, int r, int x)
{
    while (l <= r) {
        // mid is alway calculated after each iteration 
        int m = l + (r - l) / 2;
 
        // Check if x is present at mid, if present return
        if (num[m] == x)
            return m;
 
        // If x greater, ignore left half
        if (num[m] < x)
            l = m + 1;
 
        // If x is smaller, ignore right half
        else
            r = m - 1;
    }
    // if we reach here, then element was
    // not present
    return -1;
}

Time and Space Complexity

In terms of time complexity, the worst-case scenario is O(logN), where N is the number of elements in the array. The space complexity of the algorithm is O(1).

In conclusion, binary search is a powerful algorithm that can be used in various situations. By implementing it correctly, we can significantly reduce the time complexity of our code.

Peace out😊