Searching

Lesson 6 of 7 in Core Patterns · 20 min · Beginner

Choosing how to find something based on how it's stored.

Introduction

Finding a friend's number takes a couple of seconds in your phone, and ages in a drawer of loose paper slips. Why, when the question is exactly the same?

In your phone the contacts are kept in alphabetical order. Jump to P, scan a few names, and Priya is right there. You never look at most of your 500 contacts.

Now picture the same 500 numbers on paper slips, shuffled together in a drawer. Any slip could be the right one, so you read them one at a time, and in the worst case you read all 500.

Lesson overview

This lesson will show you how to:

Explain why the storage method, not the question, decides the search cost.
Trace binary search on a sorted array, halving the range each step.
Find a target in a rotated sorted array by checking which half is sorted.
Find the minimum of a rotated array by comparing mid with the right edge.
Choose scan, binary search or hashing from how the data is stored.
Spot when a hash lookup slows to O(n) because keys collide.

Array nums with 7 slots: 4, 5, 6, 7, 0, 1, 2. Pointers: lo at index 0; hi at index 6; mid at index 3. Window from index 0 to 6. Marked: index 0 compare; index 1 compare; index 2 compare; index 3 compare.

Mental model

Finding a book in a house. If the books are piled on the floor, you read every spine. If they sit on a shelf in title order, you open the middle, see whether your title comes before or after, and ignore the other half.

If the house has a catalogue that says "shelf 4, slot 12", you walk straight there. Same book, three storage styles, three very different amounts of work.

Before you pick a search, ask how the data is stored: raw means scan it, sorted means halve it, hashed means jump to it.

Words to know

linear search: Check items one at a time from the start until you find the target or run out. It works on any collection, in any order.
sorted: The items run from smallest to largest. This order is what lets one look rule out many items at once.
search space: The items that could still hold the target. A good search shrinks it fast: by one, by half, or all the way to one bucket.
rotated: A sorted list whose first few items were moved to the back, like [4, 5, 6, 7, 0, 1, 2]. It climbs, drops once, then climbs again.
pivot: The spot where a rotated list drops, from 7 down to 0 in the example. The smallest value sits right after it.
hashing: Turning a key into a number that names a bucket, so you can jump straight to where the key would be instead of scanning.
balanced BST: A binary search tree whose two sides stay about equally tall, so a search walks roughly log n levels. An unbalanced one can lean into a long chain.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: The collection is unsorted and you look something up once or twice: scan it. Sorting or building a map first costs more than the one scan.
Yes: The array is sorted, or a rotation of a sorted one, and you want O(log n): halve it with binary search, checking which half is in order if it was rotated.
Yes: You will do many lookups, the order doesn't matter, and you can spend some extra memory: put the items in a hash map and jump.
Yes: You need lookups and also order, like the next bigger value or a range, while items keep coming and going: use a balanced BST.

Not this when

No: The data is unsorted, or a linked list: halving needs order and a way to jump to the middle, and neither is there.
No: You need the next bigger key or a range: a hash map scatters the order, so those questions fall back to scanning everything.
No: You search only once: sorting first costs O(n log n) just to save an O(n) scan.

Which pattern fits?

Which pattern? 1 of 6
Find one user id in an unsorted log of a million lines. You only need to do it once.
Which pattern? 2 of 6
A sorted array of order totals, and you want the first index whose total is at least 500. It must run in O(log n).
Which pattern? 3 of 6
A stream of orders arrives, and for each one you must instantly say whether its id has been seen before.
Which pattern? 4 of 6
A sorted array of ids was rotated at an unknown spot, like [4, 5, 6, 7, 0, 1, 2]. Find the index of a target in O(log n).
Which pattern? 5 of 6
Prices are inserted and removed all day, and you must keep finding the smallest price that is at least x.
Which pattern? 6 of 6
A sorted array of numbers: do any two of them add up to a target?

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1lo = 0, hi = n − 1
while lo <= hi:
2mid = lo + (hi − lo) / 2
3if nums[mid] == target:
8return mid
4if nums[lo] <= nums[mid]: (left half is sorted)
5if nums[lo] <= target < nums[mid]:
6hi = mid − 1 (keep the left half)
else:
7lo = mid + 1 (keep the right half)
else: (right half is sorted)
5if nums[mid] < target <= nums[hi]:
7lo = mid + 1 (keep the right half)
else:
6hi = mid − 1 (keep the left half)
8return −1

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Time · O(log n)Space · O(1)

In a rotated array, at least one half around mid is always in order. nums[lo] <= nums[mid] means the left half is; otherwise the right half is. Check whether the target falls inside the sorted half, and keep that half or the other one.
This needs all values to be different. With duplicates, nums[lo] == nums[mid] == nums[hi] can hide which half is sorted, so you can only trim one cell at a time and the worst case becomes O(n). That is LeetCode 81.
To find the minimum instead (LeetCode 153), compare nums[mid] with nums[hi]. A bigger mid means the drop is to its right, so lo = mid + 1. Otherwise mid may be the minimum, so hi = mid.
Which search? Match the method to how the data is stored. Raw data and one lookup: linear scan, O(n) time and O(1) space. The scan is a loop that returns the index at the first match and −1 if none matches.
Sorted array, or a rotation of one: binary search, O(log n). Sorting first costs O(n log n), so it only pays off when you search many times.
Many lookups and order doesn't matter: a hash map, O(1) on average per lookup, with O(n) extra memory. A run of colliding keys can push one lookup toward O(n).
Lookups plus order (next bigger value, ranges) while items come and go: a balanced BST, O(log n) per operation. A BST that isn't balanced can lean into a chain and cost O(n). A linked list is always a scan, sorted or not, because you can't jump to its middle.
Finding a word on a page with Cmd+F is string search, which means matching a pattern inside text. It is a close cousin but a different problem, and this lesson is about finding an item in a collection.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

A sorted array of distinct integers was rotated at an unknown pivot. Given the rotated array nums and a target, return the index of target, or -1 if it is not there. Your solution must run in O(log n).

Input

nums = [4,5,6,7,0,1,2], target = 0

Output

Approach

Plain binary search breaks, because the array drops from 7 to 0. But at any mid, one half is still in order.
lo = 0, hi = 6, mid = 3 holds 7. nums[0] = 4 is at most 7, so the left half 4..7 is sorted. 0 isn't between 4 and 7, so drop it: lo = 4.
lo = 4, hi = 6, mid = 5 holds 1. nums[4] = 0 is at most 1, so the left half 0..1 is sorted, and 0 fits in it. Keep it: hi = 4.
Now mid = 4 holds 0, the target, so return 4. If lo ever passes hi, every cell has been ruled out, so return -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Time · O(log n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

You must check 100,000 different ids against the same unsorted list of 50,000 ids. Which plan avoids scanning the whole list 100,000 times?
In [6, 7, 8, 1, 2, 3, 4, 5], lo is 0 and mid is 3, which holds 1. Which half is sorted?
Why do we say a hash lookup is O(1) on average, rather than plain O(1)?
When is searching a binary search tree O(log n)?
Why can't rotated-array search promise O(log n) once duplicates are allowed, as in [1, 0, 1, 1, 1]?

Question 1 of 5

You must check 100,000 different ids against the same unsorted list of 50,000 ids. Which plan avoids scanning the whole list 100,000 times?

Build a hash map of the 50,000 ids once, then look each id up.Re-sort the list before every single check.Run a linear scan for every id.Run binary search directly on the unsorted list.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 7 solved

Solve Search Insert Position (opens in a new tab) (LeetCode, easy)
Hint: The array is sorted, so halve it. You want the first index whose number is at least the target, and that index is one past the end if every number is smaller.
Solve Contains Duplicate (opens in a new tab) (LeetCode, easy)
Hint: Choose how to store what you've seen. A set answers "seen this before?" in one step on average, while sorting first puts equal neighbours side by side.
Solve Search in a Binary Search Tree (opens in a new tab) (LeetCode, easy)
Hint: At each node the order of the tree tells you which single child can still hold the value, so you never need to look at both.
Solve Search a 2D Matrix II (opens in a new tab) (LeetCode, medium)
Hint: Rows and columns are sorted, but rows don't chain end to end. Start at a corner where one move gets bigger and the other gets smaller, and every comparison drops a whole row or column.
Solve Find Peak Element (opens in a new tab) (LeetCode, medium)
Hint: Nothing is sorted, yet halving works. Compare nums[mid] with its right neighbour: a peak must exist on whichever side the numbers are climbing toward.
Solve Search in Rotated Sorted Array II (opens in a new tab) (LeetCode, medium)
Hint: Same idea as the lesson, but ties can hide which half is sorted. When lo, mid and hi are equal, shrink both ends by one and carry on.
Solve Find Minimum in Rotated Sorted Array II (opens in a new tab) (LeetCode, hard)
Hint: Compare nums[mid] with nums[hi] as before, but add the tie case: when they are equal you can't tell a side, so safely drop just the last cell.

Additional resources

Binary search algorithm (Wikipedia) (opens in a new tab) — Covers the halving idea, edge cases and the usual off-by-one traps in clear detail.
Binary search (cp-algorithms) (opens in a new tab) — A practical guide to writing correct binary search loops and searching on answers.
bisect module (Python docs) (opens in a new tab) — The standard library's sorted-search helpers, with the exact semantics of insert positions.
Linear and binary search visualization (USF) (opens in a new tab) — Step through linear and binary search on a sample array and watch the range shrink.