Binary Search

Halves the search space each step by comparing the target to the middle element. Requires a sorted collection.

Complexity

Time (Best)

O(1)

Time (Avg)

O(log n)

Time (Worst)

O(log n)

Space

O(1)

Key Points

›Requires sorted input — cannot work on unsorted data
›Eliminates half the remaining search space every comparison
›O(log n) is dramatically faster than O(n) for large inputs
›Calculate mid as low + (high - low) / 2 to avoid integer overflow
›Template applies to many problems: find first/last occurrence, boundary conditions

Code Examples

Swift

func binarySearch(_ arr: [Int], target: Int) -> Int? {
    var low = 0, high = arr.count - 1
    while low <= high {
        let mid = low + (high - low) / 2
        if      arr[mid] == target { return mid }
        else if arr[mid] < target  { low  = mid + 1 }
        else                       { high = mid - 1 }
    }
    return nil
}

let sorted = [1, 3, 5, 7, 9, 11, 13, 15]
if let idx = binarySearch(sorted, target: 7) {
    print("Found at index \(idx)")  // Found at index 3
}

Practice Problems

Binary Search

EasyLeetCode ↗

First Bad Version

EasyLeetCode ↗

Search a 2D Matrix

MediumLeetCode ↗

Find Minimum in Rotated Sorted Array

MediumLeetCode ↗