Stop 20 · Data Structures & AlgorithmsTopics · 6/8

Sorting & Searching

In short

Sorted data lets you find things in a few steps instead of reading everything. That one idea powers binary search, database indexes and half the clever tricks in interview answers.

The fundamental algorithms (merge sort, quicksort, binary search) that underpin countless other algorithms and interview questions.

The purple blob opens a huge dictionary in the middle and peeks at the page.

Think of it like this

Looking up a word in a fat dictionary

To find "mango" you don't read from page one. You open the middle, see words starting with 'k', and know mango is in the right half. One flip throws away half the book. About 20 flips find any word among a million. It only works because the dictionary is sorted.

Watch it happen

Binary search for 42

1/4The list is sorted. lo starts at 0 and hi at 8, covering everything.

The big ideas

What you need to know

Binary search is O(log n)

Each look halves what's left. It only works on sorted data, so always ask whether the input is sorted.

Merge sort splits and merges

Always O(n log n) and stable, meaning equal items keep their order. It needs extra memory for merging.

Quicksort is fast on average

O(n log n) on average, but O(n²) with bad pivots. Random pivots make the worst case very unlikely.

Search the answer, not the array

"Smallest speed that finishes in time" can be binary searched over possible speeds. A favourite interview twist.

See it in code

Walk through the code

python

1def binary_search(arr, target):2    lo, hi = 0, len(arr) - 13    while lo <= hi:4        mid = (lo + hi) // 25        if arr[mid] == target:6            return mid7        if arr[mid] < target:8            lo = mid + 19        else:10            hi = mid - 111    return -112 13marks = [3, 8, 15, 21, 27, 33, 42, 50, 61]14print(binary_search(marks, 42))  # 615print(sorted([5, 2, 9], reverse=True))  # [9, 5, 2]

1/3The search space is lo to hi, inclusive. Keep going while it isn't empty.

Write binary search from memory until it's boring. In real code, Python's built-in sorted() and the bisect module do the heavy lifting.

Save yourself the pain

Common mistakes

Oops

Writing while lo < hi with hi = len(arr) - 1, then missing the last item.

Do this instead

Pick one convention and stick to it. With an inclusive hi, loop while lo <= hi and move to mid + 1 or mid - 1.

Oops

Sorting the data just to search it once.

Do this instead

Sorting costs O(n log n), more than a single O(n) scan. Sort when you'll search many times.

Your mission

Binary search three ways

~35 min

Quick check

Binary search on a sorted list of about a million items needs roughly how many comparisons in the worst case?

Go deeper

1Implement binary search from scratch and its common variants (leftmost/rightmost bound).
2Learn when each sorting algorithm's time/space trade-offs matter.
3Practice recognizing when a sorted array unlocks a binary search solution.