DSA — Searching Algorithms

Binary Search

Halve the search space each step by comparing target with the middle element. Requires a sorted array. Efficiency: O(log n).

— min read
O(log n)Time
O(1)Space
SortedRequired
Divide& Conquer
✓Interview Fav
01Step-by-Step Search
Array must be sorted. Press Find.
Logic
Code
Quiz
Practice
01
Initial Range
Set `lo = 0` and `hi = n - 1`.
02
Middle Check
Calculate `mid = (lo + hi) // 2`. If `arr[mid] == target`, done!
03
Divide
If target is larger, search right half (`lo = mid + 1`). Otherwise, search left half (`hi = mid - 1`).
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1
1. What must be true of the array before binary search works?
2. Searching 1,000,000 sorted elements takes roughly how many comparisons?
3. arr[mid] is smaller than the target. What happens next?
4. Why is mid = lo + (hi - lo) // 2 preferred over (lo + hi) // 2 in languages with fixed-width integers?
5. The loop ends with lo > hi. What does that mean?
Search Mastery0 / 3 solved
← Linear Search