Binary Search

Binary Search is a very efficient search algorithm for sorted data. It works by halving the search area at every step.

Requirement

The array must be sorted before using binary search.

Iterative Implementation

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Recursive Implementation

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

Example

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 100))  # -1

Visualization

Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Step 1: low=0, high=9, mid=4 -> arr[4]=16 < 23
Step 2: low=5, high=9, mid=7 -> arr[7]=56 > 23
Step 3: low=5, high=6, mid=5 -> arr[5]=23 = 23 ✓

Variation: Lower Bound

Finds the index of the first occurrence of the element.

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1  # Look for something smaller
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return result

Variation: Upper Bound

Finds the index of the last occurrence of the element + 1.

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            low = mid + 1  # Look for something larger
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return result

Edge Cases

# Empty array
binary_search([], 5)  # -1

# Single element
binary_search([5], 5)  # 0
binary_search([3], 5)  # -1

# Target at the start/end
binary_search([1, 2, 3, 4, 5], 1)  # 0
binary_search([1, 2, 3, 4, 5], 5)  # 4

Time Complexity

Space Complexity

• Iterative: O(1)
• Recursive: O(log n) due to the call stack

Binary Search is very efficient. Now let's study Dijkstra for shortest paths.