Binary Search in Python

Binary Search is the most efficient way to find any target element from a sorted list or array. The basic approach is to narrow down the interval by repeatedly cutting it in half. This decreases the search space significantly at every step. Here’s a detailed explanation:

How Binary Search Works

1. Precondition: The array should be sorted in ascending (or descending) order.
2. Initialization:
   • Declare two pointers: low starting at 0 and high starts at the last index.
3. Iteration:
   • Calculate the middle index: mid = (low + high) // 2.
   • Compare the middle element (arr[mid]) with the target:
     • If arr[mid] == target, the search is successful, and the index of the target is returned.
     • If arr[mid] < target, adjust the low pointer to mid + 1 to search in the right half.
     • If arr[mid] > target, adjust the high pointer to mid - 1 to search in the left half.
4. Termination:
   • If low > high, the target is not present, and the search ends.

Python Implementation

Here’s how you can implement binary search in Python:

Iterative Approach

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # Calculate mid index
        if arr[mid] == target:
            return mid  # Target found, return its index
        elif arr[mid] < target:
            low = mid + 1  # Search the right half
        else:
            high = mid - 1  # Search the left half

    return -1  # Target not found

Explanation:

1. Initialization:
   • low is set to 0 (the start of the array).
   • high is set to len(arr) - 1 (the end of the array).
2. While Loop:
   • The condition low <= high ensures that the search continues as long as there is a valid search space.
3. Calculate mid:
   • The middle index is calculated using mid = (low + high) // 2.
   • This formula avoids overflow issues common in other languages when low + high becomes too large.
4. Comparison:
   • If arr[mid] == target: The middle element matches the target, and the function returns its index.
   • If arr[mid] < target: The target must be in the right half, so the low pointer is adjusted to mid + 1.
   • If arr[mid] > target: The target must be in the left half, so the high pointer is adjusted to mid – 1.
5. End Condition:
   • If the loop is over (low > high) the function return -1, the target is nowhere in the array.

Recursive Approach

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # Base case: Target not found

    mid = (low + high) // 2  # Calculate mid index

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

Explanation:

1. Base Case:
   • When low > high, the function stops searching and returns -1 because the search space is invalid (target not found).
2. Calculation of mid:
   • Similar to the iterative method, the middle index is calculated by mid = (low + high) // 2.
3. Comparison:
   • If arr[mid] == target: the middle element equals the target and the function returns its index.
   • If arr[mid] < target: The function calls itself recursively with a new range: mid + 1 to high (right half).
   • If arr[mid] > target: The function calls itself recursively with a new range: low to mid - 1 (left half).
4. Recursive Calls:
   • The function keeps reducing the search space by half with each recursive call until the target is found or the base case is reached.
5. Return:
   • Upon finding the target, the function returns its index.
   • Otherwise, it eventually returns -1 if the target is not in the array.

Comparison of Iterative and Recursive Approaches

Example Walkthrough

Array: [1, 3, 5, 7, 9], Target: 5

1. Iterative Approach:
   • Initial: low = 0, high = 4.
   • Step 1: mid = (0 + 4) // 2 = 2, arr[mid] = 5. Target found at index 2.
2. Recursive Approach:
   • Call 1: low = 0, high = 4, mid = 2, arr[mid] = 5. Target found at index 2.

Complexity Analysis

1. Time Complexity:

• At each step, the search space is halved.
• In the worst case, the algorithm makes at most log⁡2(n) comparisons, where n is the size of the array.
• O(\log n).

2. Space Complexity:

• Iterative approach: O(1) (no extra space is used).
• Recursive approach: O(\log n) due to recursive function calls on the call stack.

Key Points to Remember

• Binary Search only works on sorted data.
• For large datasets, linear search is not as efficient as it could be.
• The algorithm assumes constant time for element comparisons.