9.3 Binary Search

Binary Search is a highly efficient algorithm for locating an element within a sorted array. It dramatically reduces the search space by dividing it in half at each step, making it significantly faster than linear search for large datasets.

How Binary Search Works

The core principle of binary search involves repeatedly dividing the search interval in half.

1. Start: Begin with the entire sorted array as your search space.
2. Midpoint: Identify the middle element of the current search space.
3. Compare:
   • If the middle element is equal to the target, you've found it! Return its index.
   • If the target is smaller than the middle element, discard the right half of the array (including the middle element) and continue searching in the left half.
   • If the target is larger than the middle element, discard the left half of the array (including the middle element) and continue searching in the right half.
4. Repeat: Continue this process of dividing and comparing until the element is found or the search space becomes empty (meaning the element is not present in the array).

Binary Search Implementations in Python

Binary search can be implemented using two primary approaches: iterative and recursive.

1. Iterative Implementation

This approach uses a while loop to manage the search space.

def binary_search_iterative(arr, target):
    """
    Performs binary search iteratively on a sorted array.

    Args:
        arr (list): A sorted list of elements.
        target: The element to search for.

    Returns:
        int: The index of the target element if found, otherwise -1.
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        # Calculate the middle index.
        # Using low + (high - low) // 2 is safer against potential integer overflow
        # in languages with fixed-size integers, though less critical in Python.
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            # Target is in the right half
            low = mid + 1
        else:
            # Target is in the left half
            high = mid - 1

    return -1  # Target not found

2. Recursive Implementation

This approach uses function calls to itself to narrow down the search space.

def binary_search_recursive(arr, target, low, high):
    """
    Performs binary search recursively on a sorted array.

    Args:
        arr (list): A sorted list of elements.
        target: The element to search for.
        low (int): The starting index of the current search space.
        high (int): The ending index of the current search space.

    Returns:
        int: The index of the target element if found, otherwise -1.
    """
    # Base case: If the search space is invalid (low > high), the element is not found.
    if low > high:
        return -1

    # Calculate the middle index.
    mid = low + (high - low) // 2

    if arr[mid] == target:
        return mid  # Target found
    elif arr[mid] > target:
        # Target is in the left half
        return binary_search_recursive(arr, target, low, mid - 1)
    else:
        # Target is in the right half
        return binary_search_recursive(arr, target, mid + 1, high)

Example Usage

my_list = [1, 3, 5, 7, 9, 11, 13, 15, 17]
search_value = 11

# Iterative Search
index_iterative = binary_search_iterative(my_list, search_value)
print(f"Iterative search for {search_value}: Found at index {index_iterative}")
# Expected Output: Iterative search for 11: Found at index 5

# Recursive Search
# Note: When calling recursively for the first time, pass the full array bounds (0 to len(arr) - 1)
index_recursive = binary_search_recursive(my_list, search_value, 0, len(my_list) - 1)
print(f"Recursive search for {search_value}: Found at index {index_recursive}")
# Expected Output: Recursive search for 11: Found at index 5

# Example for a value not in the list
search_value_not_present = 6
index_not_present = binary_search_iterative(my_list, search_value_not_present)
print(f"Iterative search for {search_value_not_present}: Found at index {index_not_present}")
# Expected Output: Iterative search for 6: Found at index -1

Time and Space Complexity

Binary search is remarkably efficient, especially compared to linear search.

* The space complexity for the recursive implementation is O(log n) due to the function call stack depth. The iterative version has O(1) space complexity as it only uses a few variables.

Key Characteristics of Binary Search

• Sorted Data Requirement: Binary search only works on sorted arrays. If the array is not sorted, the algorithm will not produce correct results and may even return false positives or negatives.
• Efficiency: It is highly efficient for searching within large datasets.
• Implementation Flexibility: It can be implemented using either an iterative or a recursive approach.
• Midpoint Calculation: When dealing with languages susceptible to integer overflow, it's recommended to calculate the midpoint as mid = low + (high - low) // 2 instead of mid = (low + high) // 2. While Python's arbitrary-precision integers mitigate this risk, it's a good practice to be aware of.

When to Use Binary Search

• When working with large, sorted datasets.
• When performance is critical, and linear search is too slow.
• As a fundamental building block in divide-and-conquer algorithms.

Common Interview Questions

• What is binary search and how does it work?
• How does binary search differ from linear search?
• What are the time and space complexities of binary search?
• How would you implement binary search iteratively in Python?
• How would you implement binary search recursively in Python?
• Why is it essential for the array to be sorted before applying binary search?
• What are the base conditions for a recursive binary search?
• How does binary search handle arrays with duplicate elements? (Note: Standard binary search might return any of the duplicate elements' indices. Variations exist to find the first or last occurrence.)
• Can binary search be applied to linked lists? Why or why not? (Answer: No, because linked lists do not support efficient random access to elements, which is required for calculating the midpoint.)
• What is the advantage of using low + (high - low) // 2 for calculating the midpoint over (low + high) // 2?