DSA Factory
Free lessonsBinary search · Stage 0 · Halving the search · Step 1

Find it by halving

Look in the middle, then throw away the half that can't hold the answer. About 9 minutes.

Look in the middle first

Think of the guessing game where someone picks a number from 1 to 100 and only says "higher" or "lower". You would start at 50. Because the list is sorted, the middle number tells you which half the value must be in.

If the middle is too small, the value can only be to its right. If it is too big, only to its left. One look, and half the list is gone.

Middle too small? The answer is to the right, so move the low marker to just past the middle.
Middle too big? The answer is to the left, so move the high marker to just before the middle.
Looking for 31target = 31
3
0
8
1
12
2
19
3
23
4
31
5
40
6
52
7
67
8
lowhigh

The middle is position 4, value 23. 31 is bigger, so 23 and everything left of it are out.

Move 1 of 3

Keep a range, not a position

Two markers, low and high, hold the part of the list that can still contain the value. Start with the whole list. Each look shrinks the range, like closing in on a word by opening a dictionary to the middle again and again.

If low passes high, the range is empty and the value isn't there.

Low not past high: there is still something to check.
Low past high: nothing is left, so answer minus one.
In code
answers = []
for x in queries:
    low, high, at = 0, len(nums) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == x:
            at = mid
            break
        if nums[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    answers.append(at)
return answers

Why not just use a set?

A set from Hashing can tell you "yes, it's there". But a sorted list is often what you are given, and halving needs no extra memory. It also tells you where the value sits.

That opens up the next steps: where a missing value would go, and how many copies there are, which a set cannot answer.

Sorted input: is the signal to think of halving first.
Quick check

You're looking for 9. The middle value is 14. What happens next?

[2, 5, 9, 14, 20, 27, 33] · low = 0, high = 6, mid = 3
  1. Ahigh = mid − 1
  2. Blow = mid + 1
  3. Chigh = mid
Show the answer

high = mid − 1. 14 is bigger than 9, so 9 can only be left of it. The range becomes positions 0 to 2.

Your problem

Find each value in a sorted list

nums is sorted from smallest to largest, with no repeats. For each value in queries, find its position in nums, or -1 if it isn't there. Return the answers in the same order as queries.

Example
nums = [3, 8, 12, 19, 23, 31, 40], queries = [23, 5, 3] → [4, -1, 0]

0 ≤ n ≤ 2,000,000 · sorted ascending, no repeats · up to 2,500 queries

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding