Binary Search : Extra Care

So you might be aware of the algorithm of Binary Search, simple one right. But there is simple bug lies in Binary Search if we don’t care at all while writing the codes and most of the beginner does same.

More Practice –

Java Bubble Sort

Here is Java Edition of Algorithm –

So what’s Bug Here or do you think everything is okay here? The Bug is in the line

In Programming Pearls Bentley says that the analogous line “sets m to the average of l and u, truncated down to the nearest integer.” On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2³¹ – 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.

This bug can manifest itself for search space is 2³⁰ or greater (roughly a billion elements).

So what’s best way to fix the Bug? Here’s the one way manually add half the range to the low number:

Do you know how this works,
Calculation without adjustment would’ve been like 5 + 10 = 15 -> 15/2 = 7.5
here, sum can cause overflow but not subtraction.
5 + (10-5)/2 == 5 + 5/2 == 5 + 2.5 == 7.5 . We calculate the average difference instead of actual average and add it to smaller number to get same results.

Second way to fix this is using logical bit shifting.

Where >>> is logical right shift operator.

Reason this works is, logical bit shift unlike arithmetic shift considers sign bit also in shift operation. When overflow happens addition operation sets sign-bit to store result. This is still valid summation but interpreting it as signed int will have wrong results.
eg,
1111 unsigned represents 31
signed represents – 15
Also as we know right shift bit operation is equivalent to dividing by 2.
So, shift considering the extra bit results,
0111. ie, 15.

Happy Exploring and Happy Coding…

Connect with us at LinkedIn –

Yogesh Joshi

What is the time complexity of binary search algorithm?

The time complexity of binary search algorithm is O(log n), where n is the number of elements in the sorted array.

How can the bug in the binary search algorithm be fixed?

The bug in the binary search algorithm can be fixed by modifying the binary search algorithm to find the first occurrence or last occurrence of the target element in the array, depending on the requirement. This can be achieved by adding extra checks while updating the search interval.

How does binary search algorithm work?

Binary search algorithm works by repeatedly dividing the search interval in half until the target element is found or the search interval is empty. At each step, the algorithm compares the middle element of the current interval with the target element and narrows down the search interval accordingly.