Searching

Linear search

def linear_search(nums, target):\n    for i, n in enumerate(nums):\n        if n == target:\n            return i\n    return -1   # O(n)

Binary search

# Requires a sorted list — O(log n)\ndef binary_search(nums, target):\n    left, right = 0, len(nums) - 1\n    while left <= right:\n        mid = (left + right) // 2\n        if nums[mid] == target:\n            return mid\n        elif nums[mid] < target:\n            left = mid + 1\n        else:\n            right = mid - 1\n    return -1\n\nbinary_search([1, 3, 5, 7, 9, 11], 9)   # 4

Why it is fast

1,000,000 items:\n  linear: up to 1,000,000 steps\n  binary: about 20 steps\n\n(log2 of 1,000,000 ≈ 20)

The pattern

Halve the search space each step by comparing the middle element. Remember: the list must be sorted first.

Common binary-search variants

• Find first/last occurrence of a value
• Find the smallest value >= target
• Find the peak in a mountain array

Practice

assert binary_search([1, 3, 5], 3) == 1\nassert binary_search([1, 3, 5], 4) == -1\nassert binary_search([], 1) == -1\nprint("ok")

Tip: Binary search is a top interview topic — code it from memory three times this week and it will stick.