Common Pitfalls in Binary Search

Small mistakes in binary search lead to infinite loops or wrong indices. Here are the most common and how to avoid them.

1. Integer Overflow in Mid

Mistake: int mid = (low + high) / 2; can overflow when low + high exceeds Integer.MAX_VALUE.

Fix: Use int mid = low + (high - low) / 2; (or unsigned right shift: (low + high) >>> 1 in Java).

2. Loop Condition: left <= right vs left < right

  • left <= right: Use when the search space is [left, right] inclusive and you want to stop when the space is empty. After the loop, left > right.
  • left < right: Use when you are narrowing to a single index; mid is often computed as left + (right - left) / 2 and you set either left = mid + 1 or right = mid. Avoids infinite loop when left == right and you set right = mid.

Choose one style and stick to it; document “search space is [left, right]” or “narrow to one index”.

3. Incorrect Shrinking (Infinite Loop)

Mistake: Writing low = mid or high = mid when you should use mid + 1 or mid - 1, so the range never shrinks when low == high or adjacent.

Fix: Always ensure the range shrinks: if you exclude mid from the next range, use mid + 1 or mid - 1. If you keep mid (e.g. “right might be answer”), use high = mid and ensure mid < high when you set it (e.g. mid = left + (right - left) / 2 with right = mid).

4. Searching in Rotated or Unsorted Data

Standard binary search assumes a sorted range. For “search in rotated sorted array”, you still compare with one half that you know is sorted and recurse there. For unsorted data, binary search on the value space (e.g. binary search on answer) is fine; binary search on indices is not.

5. Returning the Wrong Index

When the key is not found, clarify what to return: -1, insertion point, or “next greater”. Implement and test that case explicitly.

Summary

Use safe mid calculation, be consistent with loop condition and how you shrink the range, and only use index-based binary search on sorted (or known-sorted) segments. Test with one-element and two-element arrays to catch off-by-one errors.