readyforhires
Sign up free

Sorting & Binary Search 101

Fundamental · 4 chapters · 8 min read · Halve the search space every step, on arrays and on the answer itself.

Practise this in the app All guides

Why sorting and binary search go together

Order is information

Sorting costs O(n log n), but it buys a lot: equal items become neighbours, the smallest and largest are at the ends, and most importantly you can binary search. Binary search finds a position in a sorted sequence in O(log n) by comparing with the middle element and throwing away the half that cannot contain the answer. For a million elements that is about 20 comparisons.

Signals in a problem statement

Binary search on the answer

This is the version that separates strong candidates. If you can write a function ok(x) that answers "is x big enough?", and ok is monotonic (once true, it stays true for every larger x), then you can binary search over x itself, even if there is no array. Example: "What is the slowest eating speed that finishes all bananas in h hours?" Faster speeds always finish; slower ones might not. So search the speed range 1..max(piles) for the first speed where ok becomes true.

Mental model

Think of the search space as a row of answers F F F F T T T. Your job is to find the first T. Every template in the next chapter is a careful way of doing exactly that without an infinite loop.

Core patterns with templates

1. First index where a condition becomes true

This single template covers insert position, lower bound and binary search on the answer.

def first_true(lo, hi, ok):
    # search in [lo, hi); returns hi if ok is never true
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Insert position of target in sorted a: first_true(0, len(a), lambda i: a[i] >= target). Python's bisect.bisect_left(a, target) does the same thing.

2. Binary search on the answer

def min_eating_speed(piles, h):
    def ok(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    return first_true(1, max(piles) + 1, ok)

Example: piles [3, 6, 7, 11], h = 8. Speed 4 needs 1 + 2 + 2 + 3 = 8 hours, speed 3 needs 10, so the answer is 4.

3. Integer square root

def isqrt(x):
    return first_true(0, x + 2, lambda m: m * m > x) - 1

4. Rotated sorted array

One half around mid is always sorted. Decide which, then check whether the target lies inside it.

def search_rotated(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[lo] <= a[mid]:
            if a[lo] <= t < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if a[mid] < t <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

5. Custom sort order

from functools import cmp_to_key

def largest_number(nums):
    s = [str(x) for x in nums]
    s.sort(key=cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
    out = "".join(s)
    return "0" if out[0] == "0" else out

Complexity, mistakes and edge cases

Complexity

TaskTimeSpace
Python sort (Timsort)O(n log n)O(n) worst case
Binary search on an arrayO(log n)O(1)
Binary search on the answerO(log R × cost of ok)depends on ok

For Koko-style problems with range R up to 10⁹ and ok costing O(n), the total is about 30 × n operations, which is comfortably fast.

Common mistakes

Edge cases

Empty array, one element, target smaller than all or larger than all, all elements equal, rotation by 0 (not rotated), x = 0 or 1 for square root, and a list of zeros for "largest number" (answer "0", not "000").

Variations and practise

How interviewers twist it

How to explain it

Say the shape aloud: "ok(speed) is false for small speeds and true for large ones, so I binary search for the first true." This sentence alone often earns the interviewer's nod.

Practise

The problems below go from insert position and square root to rotated arrays, binary search on the answer, a custom sort comparator, and finally the median of two sorted arrays. Use one template consistently across all of them.

Practise

Easy

Medium

Hard

Practise this in the app All guides