Skip to main content

Binary Search Fundamentals

TL;DR​

Binary search eliminates half the search space each iteration on sorted arrays, achieving O(log n) time. Standard template uses left and right pointers, comparing mid to target. Two key patterns: finding element (left <= right) and finding boundary (left < right). Off-by-one errors are common: loop condition (< vs <=), mid calculation (left + (right - left) / 2 avoids overflow), return value (left, right, or -1/not found) must match intent. Master template prevents subtle bugs.

Core Concepts​

Binary Search Template​

Standard pattern: left = 0, right = n - 1. While left <= right: mid = (left + right) // 2. If arr[mid] == target, return mid. If arr[mid] < target, left = mid + 1. Else right = mid - 1. Return -1 if not found.

Left/right differences: left <= right continues until pointers cross; left < right stops when equal. Choose based on whether searching for exact match or boundary.

Mid calculation: mid = left + (right - left) // 2 prevents overflow compared to (left + right) // 2 in languages without arbitrary precision.

Left Bound and Right Bound​

Left bound finds first occurrence of target. After finding target, continue left search to find first. Template: when arr[mid] >= target, move right = mid - 1 (include mid, might be first).

Right bound finds last occurrence of target. When arr[mid] <= target, move left = mid + 1 (include mid, might be last).

Both bounds combined answer "is element present" (left bound < n and arr[left] == target), "count occurrences" (right bound - left bound + 1).

Off-by-One Errors​

Loop condition: < vs <= changes meaning. <= searches until pointers overlap; < searches for exact boundary where left/right stabilize.

Mid rounding: mid = (left + right) // 2 rounds down. Affects whether left or right half biased. Mid calculation affects loop termination and final answer.

Return value: returning mid vs left vs right or -1. After loop, left and right diverge. left typically points to insertion point for missing element.

Boundary conditions: arrays of size 0 or 1 require special handling. Empty array returns -1. Single element compares and returns 0 or -1.

Key Algorithms and Techniques​

Standard Exact Match Template​

left <= right loop, eliminate half each iteration.

Find first occurrence by continuing left search.

Find last occurrence by continuing right search.

Insertion Point Finding​

Return left when element not found (indicates insertion position).

Practical Example​

# Standard binary search
def binarySearch(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Find left bound (first occurrence)
def leftBound(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# Find right bound (last occurrence)
def rightBound(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Continue right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# Find insertion position
def searchInsert(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left  # left points to insertion position

# Count occurrences
def countOccurrences(arr, target):
    left = leftBound(arr, target)
    if left == -1:
        return 0
    right = rightBound(arr, target)
    return right - left + 1

# Test
arr = [1, 2, 2, 2, 3, 4, 5]
print(f"Search 2: {binarySearch(arr, 2)}")
print(f"Left bound 2: {leftBound(arr, 2)}")
print(f"Right bound 2: {rightBound(arr, 2)}")
print(f"Insert 2.5: {searchInsert(arr, 2.5)}")
print(f"Count 2: {countOccurrences(arr, 2)}")

Common Pitfalls​

warning

Integer overflow in mid: (left + right) // 2 can overflow. Use left + (right - left) // 2 instead.

Loop condition confusion: left <= right for exact match; left < right for boundaries. Wrong choice causes infinite loops or missed answers.

Wrong return value: After loop, left points to insertion position for missing elements. right points to last checked position. Know which to return.

Forgetting to eliminate half: If mid logic doesn't properly set left or right, search doesn't narrow. Verify eliminating exactly half each iteration.

Boundary conditions: Empty arrays, single element arrays, target outside range all require explicit handling or correct loop logic.

Self-Check​

  1. Trace binary search on [1,3,5,7] searching for 5. Show all mid values and boundary changes.
  2. Explain why left bound uses right = mid - 1 while searching continues. What's the invariant?
  3. After loop in standard search, what does left position represent?

One Takeaway​

info

Binary search's power comes from consistent halving, not complex logic. Master template: left <= right with proper mid calculation and half elimination. Boundary searches extend template by continuing after finding target. Off-by-one errors plague binary search—use standard templates and trace examples to build confidence.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.

Search space reduction​

  • Halving Search Space: Reduce search space by half each iteration
  • O(log n) Complexity: Logarithmic time complexity
  • Space Efficiency: Constant space complexity
  • Convergence: Guaranteed to find solution or determine absence

Boundary conditions​

  • Left and Right Pointers: Managing search boundaries
  • Integer Overflow: Handling large numbers in midpoint calculation
  • Empty Array: Handling edge case of empty input
  • Single Element: Handling array with one element

Implementation variations​

  • Recursive Implementation: Using recursion for binary search
  • Iterative Implementation: Using loops for binary search
  • Template Approach: Generic template for binary search problems
  • Custom Comparison: Using custom comparison functions

Search in rotated array​

  • Rotated Sorted Array: Array rotated at unknown pivot
  • Find Pivot: Locate rotation point
  • Search in Rotated Array: Find target in rotated array
  • Minimum in Rotated Array: Find minimum element