What are the pitfalls in implementing binary search?

user_36330 0
Viewed 19637

Binary search is harder to implement than it looks. "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Donald Knuth.

Which bugs are most likely to be introduced into a new binary search implementation?

binary-search algorithm
7 Answers

Here are some I can think of:

  • Off-by-one errors, when determining the boundary of the next interval
  • Handling of duplicate items, if you are suppose to return the first equal item in the array but instead returned a subsequent equal item
  • Numerical underflows/overflows when computing indices, with huge arrays
  • Recursive vs non-recursive implementation, a design choice you should consider

Are these what you have in mind?

Zach_Scrivena_200290

Read this. Java's binary search implementation hid a bug for almost a decade before anybody found it.

The bug is integer overflow. It didn't cause people problems because hardly anyone was searching big enough data structures.

user_51710

Failing to consider that when calculating the midpoint between two indices summing the high and low values may result in integer overflow.

Reference

user_129500

One bug which I encountered while implementing Binary Search is having integer range overflow while calculating the mid element. As we all know, the steps of a Binary Search implementation are:

  1. Find the Mid element.
  2. Check if:
  • Target element is greater than the mid element, search from mid+1 to end index
  • Target element is smaller than the mid element, search from start to mid-1 index
  • Target element is equal to the mid element, return the index.

In all of the above steps, recalculation of mid element is taking place. Now, mid element is found out as: mid = (start+end)/2 now, if the end index is too high(for a very big array), it might overflow the INT range. So, a better way of doing it is: mid = start + (end-start)/2

if you check carefully, ultimately, its giving us the same value, but we get rid of the overflow issue which we might encounter.

Also, as we know, binary search can be implemented on a sorted list only. Suppose in the problem it is stated that the input list is sorted, but not mentioned whether it's in Ascending or Descending order. in that case, you might need to add an extra condition to check that.

user_167669540
Related