Do you know the correct Binary Search Implementation?

Binary Search is a searching algorithm that works efficiently on sorted arrays or lists. It is also known as a logarithmic search as its cuts down the linear search time complexity of O(N) to O(logN) by repeatedly dividing the search interval in half.

Let’s understand something new!

By the time, I guess the Binary Search equation to find a element in a sorted array is on your tips.

// Fundamental Binary Search Implementation
int binarySearch(int arr[], int x, int low, int high){
    while(low <= high){
        int mid = (low + high) / 2; 
        if(arr[mid] == x) return mid; // Element Found
        else if(arr[mid] > x) high = mid - 1;
        else low = mid + 1;
    }
    return -1; // Element Not Found
}

But what if I tell you this code has some bug or might give error in some cases for particular programming languages? Yes, you heard it right.

The bug or error that you may encounter is OVERFLOW.
Note: This overflow error you may only encounter in the languages that have defined data types with maximum range like C++, Java. But in case of Python, it will not cause overflow or such error as Python can handle large values due to undeclared data type size.

This basically means the sum of low and high may go out of the bound of the data type that we have taken for large values.
One may argue, that they could take data type as “long long” in C++, then yes it will be solved(no error may occur) but understand why to take large memory size for the variable that could be solved with the “int” memory size.

Let’s assume for a minute you’re using unsigned chars (same applies to larger integers of course).

If L is 100 and R is 200, the first version is:

// low = 100, high = 200
mid = (100 + 200) / 2 = 300 / 2 = 22

Here, 100+200 overflows (because the largest unsigned char is 255), and you get 100+200 = 44 (unsigned no. addition).

I hope you got the point here, so now let’s move to its simple solution.

// Corrected Binary Search Implementation
int binarySearch(int arr[], int x, int low, int high){
    while(low <= high){
        int mid = low + (high - low) / 2; 
        if(arr[mid] == x) return mid; // Element Found
        else if(arr[mid] > x) high = mid - 1;
        else low = mid + 1;
    }
    return -1; // Element Not Found
}

Yes, I know you might think both the equation are same. You guessed right but please try to think of the difference here. (We are not making our high value higher, instead we’re reducing it and then adding it to the low value.)

low + (high - low) / 2 = (low + high) / 2
// How?
// Proof:
// (low + high) / 2 => (2low + high - low) / 2 => low + (high - low) / 2

Taking the previous example,

// low = 100, high = 200
M = 100 + (200-100) / 2 = 100 + 100 / 2 = 150

Here, No overflow occurred. We got the desired result without going out of the limits.
To experience this error practically try your hands on over here: First-bad-Version

Solved, the above question? I hope you got this error while solving with C++ or Java language.

Conclusion: Both the ways to implement Binary Search are correct. Even when Binary Search Algorithm was first discovered its implementation was [(high + low) / 2]. But, as we encounter this problem of overflow, we optimized it to [low + (high — low) / 2].
So, from next time use the updated implementation of Binary Search despite the fact it may cause overflow or not. But to make values range more feasible and less memory consumable.

Thanks for reading, do let me know in case you have any queries or if you know any more such bugs or problems.
Happy Coding!!!
Connect with me: https://linktr.ee/aadijain7