How Binary Search Works

Binary search requires a sorted list. Each step cuts the remaining search space in half by checking the middle element.

1. Find the middle element
2. If it equals the target, done
3. If target is less, search the left half
4. If target is greater, search the right half
5. Repeat until found or space is empty

data = [2,5,8,12,16,23,38,56]
target = 23
low, high = 0, len(data)-1
while low <= high:
    mid = (low+high) // 2
    if data[mid] == target:
        print(mid); break
    elif data[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

data <- [2,5,8,12,16,23,38,56]
target <- 23
low <- 1
high <- LENGTH(data)
REPEAT UNTIL low > high
{
    mid <- (low+high) DIV 2
    IF data[mid] = target
    { DISPLAY(mid) }
    ELSE IF data[mid] < target
    { low <- mid+1 }
    ELSE { high <- mid-1 }
}

Binary vs Linear Efficiency

Linear search worst case: n checks. Binary search worst case: log₂n checks.

• 8 elements: at most 3 checks
• 1,000 elements: at most 10 checks
• 1,000,000 elements: at most 20 checks

Tradeoff: binary search only works on sorted data.

Practice Problems