Common Algorithms

Binary Search

When searching through large sorted datasets like dictionaries, phone directories, or database indexes, checking every element would be impractical. Binary search dramatically reduces search time by eliminating half the remaining elements with each comparison, making it essential for efficient lookups in sorted collections.

Comparison with Linear Search

basic.py 
# Basic binary search (iterative)


def binary_search(arr, target):
    """Binary search in sorted array, return index or -1"""
    low = 0
    high = len(arr) - 1

    # Iterative binary search
    while low <= high:
        mid = (low + high) // 2

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

    return -1  # not found


# Test binary search
sorted_list = 

print("List:", sorted_list)
print("Search 7:", binary_search(sorted_list, 7))
print("Search 1:", binary_search(sorted_list, 1))
print("Search 19:", binary_search(sorted_list, 19))
print("Search 10:", binary_search(sorted_list, 10))


# Basic binary search (iterative)


def binary_search(arr, target):
    """Binary search in sorted array, return index or -1"""
    low = 0
    high = len(arr) - 1

    # Iterative binary search
    while low <= high:
        mid = (low + high) // 2

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

    return -1  # not found


# Test binary search
sorted_list = 

print("List:", sorted_list)
print("Search 7:", binary_search(sorted_list, 7))
print("Search 1:", binary_search(sorted_list, 1))
print("Search 19:", binary_search(sorted_list, 19))
print("Search 10:", binary_search(sorted_list, 10))


# Basic binary search (iterative)


def binary_search(arr, target):
    """Binary search in sorted array, return index or -1"""
    low = 0
    high = len(arr) - 1

    # Iterative binary search
    while low <= high:
        mid = (low + high) // 2

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

    return -1  # not found


# Test binary search
sorted_list = 

print("List:", sorted_list)
print("Search 7:", binary_search(sorted_list, 7))
print("Search 1:", binary_search(sorted_list, 1))
print("Search 19:", binary_search(sorted_list, 19))
print("Search 10:", binary_search(sorted_list, 10))
recursive.py 
# Recursive binary search


def binary_search_recursive(arr, target, low, high):
    """Recursive binary search implementation"""
    # Base case: search space exhausted
    if low > high:
        return -1  # not found

    # Recursive case
    mid = (low + high) // 2

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


def binary_search(arr, target):
    """Binary search wrapper"""
    return binary_search_recursive(arr, target, 0, len(arr) - 1)


# Test recursive binary search
sorted_list = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]

print("List:", sorted_list)
print("Search 23:", binary_search(sorted_list, 23))
print("Search 2:", binary_search(sorted_list, 2))
print("Search 100:", binary_search(sorted_list, 100))
trace.py 
# Binary search with trace


def binary_search_trace(arr, target):
    """Binary search with step-by-step trace"""
    low = 0
    high = len(arr) - 1
    iteration = 0

    # Trace each step
    while low <= high:
        iteration += 1
        mid = (low + high) // 2

        print(
            f"Iter {iteration}: low={low}, mid={mid}, high={high}, arr[mid]={arr[mid]}"
        )

        if arr[mid] == target:
            print(f"Found at index {mid}")
            return mid
        elif arr[mid] < target:
            print("  Target > mid, search right")
            low = mid + 1
        else:
            print("  Target < mid, search left")
            high = mid - 1

    print("Not found")
    return -1


# Test with trace
sorted_list = [10, 20, 30, 40, 50, 60, 70, 80, 90]

print("Searching for 70:")
binary_search_trace(sorted_list, 70)

print("\nSearching for 25:")
binary_search_trace(sorted_list, 25)
insertion_point.py 
# Find insertion point


def find_insertion_point(arr, value):
    """Find index where value should be inserted to maintain sort order"""
    low = 0
    high = len(arr) - 1

    # Modified binary search for insertion point
    while low <= high:
        mid = (low + high) // 2

        if arr[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return low  # insertion point


# Test insertion point finding
sorted_list = [10, 20, 30, 40, 50, 60, 70]

print("List:", sorted_list)
print("Insert 25 at index:", find_insertion_point(sorted_list, 25))
print("Insert 5 at index:", find_insertion_point(sorted_list, 5))
print("Insert 75 at index:", find_insertion_point(sorted_list, 75))
print("Insert 40 at index:", find_insertion_point(sorted_list, 40))
comparison.py 
# Compare with linear search


def linear_search(arr, target):
    """Linear search with comparison count"""
    comparisons = 0
    for i in range(len(arr)):
        comparisons += 1
        if arr[i] == target:
            print(f"  Linear: {comparisons} comparisons")
            return i
    print(f"  Linear: {comparisons} comparisons (not found)")
    return -1


def binary_search(arr, target):
    """Binary search with comparison count"""
    low, high = 0, len(arr) - 1
    comparisons = 0

    while low <= high:
        comparisons += 1
        mid = (low + high) // 2

        if arr[mid] == target:
            print(f"  Binary: {comparisons} comparisons")
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    print(f"  Binary: {comparisons} comparisons (not found)")
    return -1


# Compare performance
# Create large sorted list
sorted_list = [i * 2 for i in range(1000)]  # even numbers 0, 2, 4, ..., 1998

print(f"List size: {len(sorted_list)}")
print("\nSearch for 998:")
linear_search(sorted_list, 998)
binary_search(sorted_list, 998)

print("\nSearch for 1999 (not found):")
linear_search(sorted_list, 1999)
binary_search(sorted_list, 1999)

| Size | Linear (worst) | Binary (worst) | |------|----------------|----------------| | 10 | 10 | 4 | | 100 | 100 | 7 | | 1000 | 1000 | 10 | | 1M | 1,000,000 | 20 |

Characteristics

  • Time complexity: O(log n) - much faster than linear search
  • Space complexity: O(1) iterative, O(log n) recursive
  • Requires: sorted list
  • Best case: O(1) - target is at middle
  • Worst case: O(log n) - target not found or at edge

When to Use

  • Large sorted lists
  • Multiple searches on same data
  • When speed matters
  • Data does not change often
divide_eliminate Each comparison eliminates half the remaining search space
recursive_binary Express binary search as a recursive function with narrowing bounds
insertion_point Find where an element should be inserted to maintain sorted order
logarithmic_time O(log n) means doubling the data only adds one more step

Exercise: practical.py

Implement a function that uses binary search to find the closest value to a target in a sorted list