DSA | Binary Search | Solution for Mistake which took around 9 years to surface

In the last article https://www.techlearnings.org/single-post/dsa-binary-search-mistake-which-took-around-9-years-to-surface, we talked about the concept of Binary Search and the mistake in the code. Today let's talk about the solution.

We already know, that the problem was with computing the mid which caused overflow which means we've to devise a way such that overflow does not occur at this line.

Buggy code statement:

int mid = (low + high) / 2;

Solution Approach #1:

int mid = low + (high - low) / 2;

Solution Approach #2: Using unsigned right shift operator to shift the bits by 1

int mid = (low + high) >>> 1;

About Unsigned Right Shift Operator:

It shifts the bits of the left operand towards the right by the number of places specified by the right operand. The excess bits shifted to the right are discarded and the left-shifted bits are filled with zeros.

e.g. 1000 represents 8 in decimal. If we right shift by 1, then the new binary representation becomes 0100 which represents 4 in decimal.

In last article we wrote iterative implementation, let's end today by writing recursive implementation.

int binarySearch(int[] arr, int element, int low, int high) {
    
    if(low <= high) {
        int mid = low + (high - low) / 2;
        
        if(arr[mid] == element) {
            return mid;
        }
        if(element > arr[mid]) {
            return binarySearch(arr, element, mid + 1, high)
        }
        return binarySearch(arr, element, low, mid - 1);
    }
    return -1; 
}

Remember, space complexity for recursive implementation of binary search is O(logN) whereas for iterative implementation it's O(1). Time complexity is O(logN) in both cases.

There are a bunch of articles e.g Circuit Breaker Design Pattern, and the OAuth series already published; do go through them if you're interested to learn more.

Stay connected on LinkedIn, Facebook, Twitter, YouTube, or wherever you feel comfortable. See you soon with the next article!

Till then, Keep Learning, Happy Tech Learnings!