Search Algorithms O(log n) vs O(n) in Python

Search Algorithm Comparison: O(n) vs. O(log n) for Developers

On arrays with millions of elements, linear search may require up to 10 million operations—while binary search completes in just 24 comparisons. We break down four search algorithms in Python, covering time complexity, practical trade-offs, and real-world selection guidance. Includes overflow-safe implementations, lower_bound/upper_bound, and LeetCode-ready examples.

The search problem: given a collection arr, find the index of target, or return -1. The collection may be sorted or unsorted, static or dynamic. Real-world use cases include SKU lookup in e-commerce (millions of SKUs) and transaction ID validation in fintech.

Linear Search for Unsorted Data

Works with any collection. Checks elements sequentially.

Implementation:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Complexity:

• Time: O(n) worst/average, O(1) best.
• Space: O(1).

Binary Search and Its Variants

Requires a sorted array. Repeatedly halves the search interval.

Iterative implementation: Use mid = left + (right - left) // 2 to prevent integer overflow (critical in C++/Java; safe but idiomatic in Python).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Example
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Complexity: O(log n) time, O(1) space.

lower_bound returns the leftmost insertion position for target; upper_bound returns the rightmost. Essential for handling duplicates and solving LeetCode problems like "Find First and Last Position of Element in Sorted Array."

Exponential Search for Streaming or Unknown-Size Data

Ideal for sorted arrays of unknown length—or when target is likely near the start. First identifies a bounding range via exponential growth, then applies binary search.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Complexity: O(log i), where i is the target’s index; worst-case O(log n); space O(1).

Hash-Based Search for Dynamic Collections

Average O(1) lookup using hash tables (set/dict in Python).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Example
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Complexity: O(1) average, O(n) worst-case (hash collisions), space O(n).

Algorithm Selection Guidelines

• Unsorted array: Linear search for N < 100 or infrequent lookups.
• Sorted & static data: Binary search.
• Dynamic data with frequent inserts: Hash table (order doesn’t matter).
• Streaming or unknown-size data: Exponential search.

| Algorithm | Avg. Time | Worst Time | Space | Requirements |

|-----------|-----------|------------|-------|--------------|

| Linear | O(n) | O(n) | O(1) | Any |

| Binary | O(log n) | O(log n) | O(1) | Sorted |

| Exponential | O(log i) | O(log n) | O(1) | Sorted |

| Hash | O(1) | O(n) | O(n) | Hashable keys |

Key Takeaways

• For 10M elements: binary search takes ~24 comparisons vs. 10M for linear search.
• Always prefer overflow-safe mid calculation in binary search—even in Python, it’s a robust habit.
• Hash tables trade memory (O(n)) for blazing-fast average lookup (O(1)).
• lower_bound and upper_bound are indispensable for duplicate handling and insertion logic.
• Exponential search shines when targets cluster near the beginning of massive sorted arrays.

— Editorial Team