SoftwareInLevels

Understanding Binary Search: Implementation Guide

Learn how to implement binary search correctly with code examples in Python, Java, and C++. Master edge cases, integer overflow prevention, and production-ready patterns.

Author

Mr. Oz

Date

Read

8 mins

Level 2
Binary search code visualization showing pointers, edge cases, and common implementation patterns

Author

Mr. Oz

Date

Read

8 mins

Share

Twitter YouTube

Now that you understand the intuition behind binary search, let's dive into the implementation details. We'll cover code in multiple languages, edge cases, and production-ready patterns.

The Core Algorithm

Here's the basic structure of binary search:

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Not found

Critical: Integer Overflow

Never calculate mid as: mid = (left + right) / 2

Always use: mid = left + (right - left) / 2

Why? Because left + right can overflow when both are large positive integers near the maximum value!

Common Edge Cases

  • Empty array: Loop doesn't execute, returns -1 correctly
  • Single element: Checks that element directly
  • Target at boundaries: First or last element
  • Target not present: Eventually left > right, returns -1
  • Duplicate elements: Returns any matching index (not guaranteed to be first)

Why This Matters

Binary search is O(log n), which means:

  • 1,000 elements → ~10 comparisons max
  • 1,000,000 elements → ~20 comparisons max
  • 1,000,000,000 elements → ~30 comparisons max

Compare this to linear search's O(n) where you might need a million comparisons for a million elements!

When to Use Binary Search

  • The array is sorted (ascending or descending)
  • You need to find (or insert) an element quickly
  • Random access is available (array, not linked list)
  • You're doing many searches on the same dataset

Ready for the deep dive?

← Level 1 Level 3 →

Key Takeaways

  • Mid calculation — Always use left + (right - left) / 2 to prevent overflow
  • Loop condition — Use while left <= right (not <)
  • Pointer updates — Use mid + 1 and mid - 1 (not mid)
  • Time complexity — O(log n) because we halve the search space each iteration
  • Space complexity — O(1) as we only use a few pointers

All Levels