Binary Search in Python

Binary search is a highly efficient algorithm for finding a specific element within a sorted list.

This article provides a comprehensive guide on how to implement binary search in Python, complete with clear explanations, practical examples, and common use cases.
We’ll cover various implementations and optimization techniques for the binary search algorithm in Python to make you a pro in no time. Understanding binary search is crucial for any Python developer dealing with sorted data.

Here’s an example of how binary search can quickly locate a number in a sorted list:

sorted_list = [2, 5, 7, 8, 11, 12]
target = 13

#  Binary search function (implementation will be shown later)
def binary_search(list, target):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None

result = binary_search(sorted_list, target)

if result is not None:
    print(f"Target found at index: {result}")
else:
    print("Target not found in the list.")

Target not found in the list.

Method 1: Implementing Binary Search with Iteration

This method demonstrates the most common iterative approach to performing binary search. It involves repeatedly dividing the search interval in half until the target value is found or the interval is empty.

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

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.

    Returns:
        The index of the target value if found, otherwise None.
    """
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2  # Calculate the middle index
        guess = sorted_list[mid]

        if guess == target:
            return mid  # Target found!
        elif guess > target:
            high = mid - 1  # Adjust the high boundary
        else:
            low = mid + 1  # Adjust the low boundary

    return None  # Target not found

# Example usage:
my_list = [2, 5, 7, 8, 11, 12, 16, 20]
target_value = 12
result_index = binary_search_iterative(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

target_value = 13 #Let's test with value that not included
result_index = binary_search_iterative(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

Target 12 found at index: 5
Target 13 not found in the list.

Explanation:

• We initialize low and high to the start and end indices of the list, respectively.
• The while loop continues as long as low is less than or equal to high.
• Inside the loop, we calculate the middle index (mid) and compare the value at that index (guess) with the target.
• If guess equals the target, we’ve found the target and return its index.
• If guess is greater than the target, we adjust the high boundary to mid - 1, indicating that the target (if it exists) must be in the left half of the current interval.
• If guess is less than the target, we adjust the low boundary to mid + 1, indicating that the target (if it exists) must be in the right half of the current interval.
• If the loop finishes without finding the target, we return None.

Method 2: Implementing Binary Search Recursively

This method showcases how binary search can be implemented using recursion. Each recursive call narrows down the search space until the target is found or the search space is exhausted.

def binary_search_recursive(sorted_list, target, low=0, high=None):
    """
    Performs binary search recursively on a sorted list.

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.
        low: The lower bound of the search interval (default: 0).
        high: The upper bound of the search interval (default: len(sorted_list) - 1).

    Returns:
        The index of the target value if found, otherwise None.
    """
    if high is None:
        high = len(sorted_list) - 1

    if low > high:
        return None  # Base case: Target not found

    mid = (low + high) // 2
    guess = sorted_list[mid]

    if guess == target:
        return mid  # Base case: Target found!
    elif guess > target:
        return binary_search_recursive(sorted_list, target, low, mid - 1) #Recursive with left part
    else:
        return binary_search_recursive(sorted_list, target, mid + 1, high) #Recursive with right part

# Example usage:
my_list = [2, 5, 7, 8, 11, 12, 16, 20]
target_value = 12
result_index = binary_search_recursive(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

target_value = 13 #Let's test with value that not included
result_index = binary_search_recursive(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

Target 12 found at index: 5
Target 13 not found in the list.

Explanation:

• The base case for the recursion is when low becomes greater than high, meaning the target is not in the list, and we return None.
• Otherwise, we calculate the middle index (mid) and compare the value at that index (guess) with the target.
• If guess equals the target, we’ve found the target and return its index.
• If guess is greater than the target, we recursively call the function with the updated high value (mid - 1).
• If guess is less than the target, we recursively call the function with the updated low value (mid + 1).

Method 3: Binary Search with Error Handling

This method enhances the basic binary search implementation by adding error handling to gracefully handle invalid input, such as unsorted lists.

def binary_search_with_error_handling(sorted_list, target):
    """
    Performs binary search on a sorted list with error handling.

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.

    Returns:
        The index of the target value if found, otherwise None.
        Raises ValueError if the input list is not sorted.
    """
    if not all(sorted_list[i] <= sorted_list[i+1] for i in range(len(sorted_list)-1)):
        raise ValueError("Input list must be sorted.")

    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = sorted_list[mid]

        if guess == target:
            return mid
        elif guess > target:
            high = mid - 1
        else:
            low = mid + 1

    return None

# Example usage:
my_list = [2, 5, 7, 8, 11, 12, 16, 20]
target_value = 12
result_index = binary_search_with_error_handling(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

# Example with an unsorted list to test error handling:
unsorted_list = [5, 2, 7, 8, 11, 12, 16, 20]
target_value = 12
try:
    result_index = binary_search_with_error_handling(unsorted_list, target_value)
    if result_index is not None:
        print(f"Target {target_value} found at index: {result_index}")
    else:
        print(f"Target {target_value} not found in the list.")
except ValueError as e:
    print(f"Error: {e}")

Target 12 found at index: 5
Error: Input list must be sorted.

Explanation:

• The function first checks if the input list is sorted using all(sorted_list[i] <= sorted_list[i+1] for i in range(len(sorted_list)-1)).
• If the list is not sorted, it raises a ValueError with an informative message.
• If the list is sorted, it proceeds with the standard binary search algorithm as described in Method 1.
• The try...except block in the example usage demonstrates how to catch the ValueError and handle it gracefully.

Method 4: Binary Search Using `bisect` Module

Python's `bisect` module provides functions for performing binary search. This method leverages `bisect_left` and `bisect_right` functions to efficiently find the insertion point for a value in a sorted list.

import bisect

def binary_search_bisect(sorted_list, target):
    """
    Performs binary search using the bisect module.

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.

    Returns:
        The index of the target value if found, otherwise None.
    """
    i = bisect.bisect_left(sorted_list, target)
    if i != len(sorted_list) and sorted_list[i] == target:
        return i
    else:
        return None

# Example usage:
my_list = [2, 5, 7, 8, 11, 12, 16, 20]
target_value = 12
result_index = binary_search_bisect(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

target_value = 13 #Let's test with value that not included
result_index = binary_search_bisect(my_list, target_value)

if result_index is not None:
    print(f"Target {target_value} found at index: {result_index}")
else:
    print(f"Target {target_value} not found in the list.")

Target 12 found at index: 5
Target 13 not found in the list.

Explanation:

• bisect.bisect_left(sorted_list, target) returns the index where the target should be inserted to maintain the sorted order (i.e., the index of the first element greater than or equal to the target).
• We then check if the returned index i is within the bounds of the list and if the element at that index is actually equal to the target.
• If both conditions are true, we've found the target and return its index. Otherwise, the target is not in the list, and we return None.

Method 5: Finding First and Last Occurrence of a Value

This method shows how to find the indices of the first and last occurrences of a given value in a sorted list using a modified binary search approach.

def find_first_occurrence(sorted_list, target):
    """
    Finds the index of the first occurrence of a target value in a sorted list.

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.

    Returns:
        The index of the first occurrence if found, otherwise None.
    """
    low = 0
    high = len(sorted_list) - 1
    first_occurrence = None

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            first_occurrence = mid
            high = mid - 1  # Continue searching on the left side
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return first_occurrence

def find_last_occurrence(sorted_list, target):
    """
    Finds the index of the last occurrence of a target value in a sorted list.

    Args:
        sorted_list: The sorted list to search.
        target: The value to search for.

    Returns:
        The index of the last occurrence if found, otherwise None.
    """
    low = 0
    high = len(sorted_list) - 1
    last_occurrence = None

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            last_occurrence = mid
            low = mid + 1  # Continue searching on the right side
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return last_occurrence

# Example usage:
my_list = [2, 5, 7, 8, 8, 8, 11, 12, 16, 20]
target_value = 8

first = find_first_occurrence(my_list, target_value)
last = find_last_occurrence(my_list, target_value)

if first is not None and last is not None:
    print(f"First occurrence of {target_value} at index: {first}")
    print(f"Last occurrence of {target_value} at index: {last}")
else:
    print(f"{target_value} not found in the list.")

First occurrence of 8 at index: 3
Last occurrence of 8 at index: 5

Explanation:

• Finding First Occurrence: When the target is found at mid, we record the index and continue searching on the left side (high = mid - 1) to find the earliest occurrence.
• Finding Last Occurrence: When the target is found at mid, we record the index and continue searching on the right side (low = mid + 1) to find the latest occurrence.