What is Binary Search?

Binary search is an efficient algorithm to find the position of a target value within a sorted array or list. It operates by dividing the search interval in half repeatedly:

  1. Compare the target value to the middle element.
  2. If the target matches the middle element, return its index.
  3. If the target is smaller, search the left half of the array.
  4. If the target is larger, search the right half of the array.
  5. Repeat until the target is found or the search interval is empty.

Key Characteristics:

  • Requires a sorted array.
  • Time complexity: \(O(\log n)\).
  • Space complexity: \(O(1)\) for iterative implementation and \(O(\log n)\) for recursive implementation.

How to Apply Binary Search

Steps:

  1. Determine the Search Interval: Identify the sorted array or range to search in.
  2. Set the Pointers:
    • Initialize two pointers: left (start of the array) and right (end of the array).
  3. Iterate or Recur:
    • Calculate the middle index: \[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]
    • Compare the middle element with the target.
    • Update the pointers (left or right) to narrow the search interval.
  4. Exit Condition:
    • If left > right, the target does not exist.
    • Otherwise, return the index of the target.

Pseudocode

Iterative Implementation:

def binary_search(array, target):
    left = 0
    right = len(array) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Target not found

Recurrsive Implementation

def binary_search(array, target, left, right):
    if left > right:
        return -1  # Target not found
    
    mid = left + (right - left) // 2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        return binary_search(array, target, mid + 1, right)
    else:
        return binary_search(array, target, left, mid - 1)

Common Questions

1. Why is mid calculated like that?

In binary search, the formula for calculating the middle index is:

\[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]

This formula is designed to avoid integer overflow in programming languages where integers have a fixed range, such as C++ and Java. Here’s a detailed explanation:

Explanation

  1. Standard Calculation: The straightforward way to compute the middle index is:

    \[ \text{mid} = \frac{\text{left} + \text{right}}{2} \]

    While this formula is simple and works in many cases, it has a potential issue: if left and right are very large integers, their sum (left + right) can exceed the maximum integer value, causing integer overflow.

  2. Alternative Formula: To prevent overflow, the formula is rewritten as:

    \[ \text{mid} = \text{left} + \frac{\text{right} - \text{left}}{2} \]

    This calculates the middle index without directly adding left and right.

    • The term \((\text{right} - \text{left})\) represents the distance between left and right, which is much smaller than their sum.
    • Dividing this distance by 2 gives the offset from left to the midpoint.
    • Adding this offset back to left ensures the calculation remains within safe bounds.

In Python, using (l + r) // 2 in binary search is safe because Python’s integers are arbitrary-precision and do not overflow since Python dynamically expands integers as needed. However, in languages with fixed integer limits such as C++ and Java (e.g., INT_MAX = 2^31 - 1), calculating the middle index as (l + r) // 2 can lead to integer overflow when l and r are large. In this case, we should use l + (r - l) // 2.

Classic LeetCode Problems 🔗