Stop 21 · Data Structures & AlgorithmsTopics · 17/17

Searching

In short

Searching is more than 'loop until you find it'. Picking the right search for the data you have is often the whole point of the interview question.

Algorithms and techniques for finding an element or condition within a data set — from linear search to binary search to more specialized graph search.

The jaadu pulls the right parcel from tidy post office shelves beside a messy heap.

Think of it like this

Finding your parcel at the post office

If parcels are thrown in a heap, you check each one. If they're stacked by PIN code, you jump to the right shelf. If there's a register of tracking numbers, the clerk finds it in one look. Same parcel, three speeds.

Watch it happen

Smallest pages per day to finish 30 pages in 4 days

mid

1/4lo = 1, hi = 10. Try mid = 5 pages a day: that needs 6 days. Too slow, so lo = 6.

The big ideas

What you need to know

Linear search, O(n)

Check every item. It's the only choice for unsorted data you search just once.

Binary search, O(log n)

Works on sorted or monotonic data by halving the range each step.

Hash lookup, O(1) average

Build a Set or Map once, then every search after that is instant.

Search the answer space

When 'is x enough?' flips from no to yes at some point, binary search for that point.

How it works

Choosing how to search

1
How many searches?
One search on unsorted data? A simple loop is fine.
2
Is the data sorted?
Then binary search gives O(log n) with no extra memory.
3
Many searches, unsorted?
Build a Set or Map once, then look up in O(1).
4
Searching for a value, not an item?
Check if 'is x enough?' is monotonic and binary search over x.

See it in code

Walk through the code

1// Smallest x in [lo, hi] where ok(x) is true.2// ok must be false, false, ..., true, true (monotonic).3function firstTrue(lo, hi, ok) {4  while (lo < hi) {5    const mid = Math.floor((lo + hi) / 2);6    if (ok(mid)) hi = mid;   // mid might be the answer7    else lo = mid + 1;       // answer is to the right8  }9  return lo;10}11 12// Smallest daily pages to finish 300 pages in 7 days13firstTrue(1, 300, (pages) => Math.ceil(300 / pages) <= 7); // 43

1/4Keep halving the range of possible answers.

This 'first true' template runs in O(log(hi - lo)) checks. Note hi = mid, not mid - 1, because mid itself could be the answer.

Save yourself the pain

Common mistakes

Oops

Calling arr.includes(x) inside a loop over another big array.

Do this instead

Turn one array into a Set first. Then each check is O(1) instead of O(n).

Oops

Sorting the data just to search it once.

Do this instead

Sorting costs O(n log n), which is slower than one O(n) linear search. Sort only if you'll search many times.

Your mission

Pick the right search

~35 min

Quick check

You have an unsorted array of 10,000 IDs and must check 10,000 other IDs against it. What's the best approach?

Go deeper

1Compare linear search vs binary search performance conceptually on a large dataset.
2Practice recognizing which search technique fits a given problem's structure.
3Combine searching with other structures — e.g. binary search on the answer, a common advanced pattern.