Binary Search

Binary Search is an efficient algorithm for finding an element in a sorted array. By repeatedly dividing the search interval in half, Binary Search achieves a time complexity of O(log n). However, Binary Search can be adapted to handle specific scenarios like searching in an infinite array or searching in a rotated sorted array.

Let’s examine the standard Binary Search approach and explore how to adapt it for these specialized cases, including code examples, common pitfalls, and tips.

Standard Binary Search

Binary Search works by:

1. Starting with a range: Initialize left as the first index and right as the last index of the array.

2. Calculating the Middle Index: Calculate the middle index and compare the middle element with the target.

3. Adjusting the Range: If the middle element is equal to the target, return the index. If the middle element is greater than the target, adjust right to mid - 1; if it is less, adjust left to mid + 1.

4. Repeat until the target is found or the range invalidates (left > right).

Here’s the standard implementation of Binary Search:

from typing import List

def binary_search(arr: List[int], target: int) -> int:
    """
    Perform binary search on a sorted array to find the target.
    - arr: List of sorted integers
    - target: Integer to search for
    Returns the index of the target if found; otherwise, -1.
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # Calculate mid to prevent overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found

Binary Search in an “Infinite Array”

When working with an infinite array (or a large array where the size is unknown), we cannot directly access the last index. Instead, we need a modified approach to perform binary search in such a scenario.

Key Idea:

• Expand the Range Exponentially: Start with a small range (e.g., left \= 0, right \= 1) and keep doubling the right index until the target is less than or equal to the element at right.
• Perform Binary Search within the Range: Once the target is within a range [left, right], perform a standard binary search within this range.

Code Example for Infinite Array Search

def infinite_array_search(arr, target: int) -> int:
    """
    Search for a target in a hypothetically infinite sorted array.
    - arr: A sorted array with an unknown size (assumed to be infinite for this problem)
    - target: The integer to search for
    Returns the index of the target if found; otherwise, -1.
    """
    # Step 1: Find the range where target could be
    left, right = 0, 1
    while target > arr[right]:  # Expand the range exponentially
        left = right
        right *= 2  # Double the range size
    
    # Step 2: Perform binary search within the range [left, right]
    return binary_search(arr[left:right + 1], target)  # Slice arr for binary search

Explanation

1. Expanding the Range: By doubling right, we increase the search space exponentially, which minimizes the number of comparisons while quickly covering a large range.

• Binary Search in the Range: Once the target is within a known range, we slice arr and perform binary search within [left, right].

Binary Search in a Rotated Sorted Array

A rotated sorted array is an array that was originally sorted but then rotated at an unknown pivot. For example, [4, 5, 6, 7, 0, 1, 2] is a rotated version of [0, 1, 2, 4, 5, 6, 7].

Key Idea:

1. Binary Search with Condition Checks: Unlike standard Binary Search, we need to determine which side (left or right) of the array is sorted and whether the target lies within that sorted range.

2. Adjust the Range Accordingly: Use conditions to narrow down the search space based on the properties of the rotated array.

Code Example for Rotated Array Search

def rotated_array_search(arr: List[int], target: int) -> int:
    """
    Search for a target in a rotated sorted array.
    - arr: List of integers, sorted then rotated at an unknown pivot
    - target: Integer to search for
    Returns the index of the target if found; otherwise, -1.
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        # Check if the middle element is the target
        if arr[mid] == target:
            return mid
        # Determine if the left half is sorted
        if arr[left] <= arr[mid]:
            # Target is in the sorted left half
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Otherwise, the right half must be sorted
        else:
            # Target is in the sorted right half
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1  # Target not found

Explanation

Identify Sorted Half:

• If arr[left] <\= arr[mid], the left half is sorted.
• If arr[mid] <\= arr[right], the right half is sorted.

Adjust Search Space:

• If the left half is sorted and the target is within the range [arr[left], arr[mid]], narrow the search to the left half.
• Otherwise, if the right half is sorted and the target is within [arr[mid], arr[right]], narrow the search to the right half.

Example Execution: For an array [4, 5, 6, 7, 0, 1, 2] with target \= 0:

1. The midpoint is 7, which is greater than 4, indicating that the left half is sorted.
2. Since 0 is not within [4, 7], search in the right half.
3. Continue until 0 is found at the correct index.