Raffle Stub Lookup
You run the raffle at a school fair. Every ticket you sold left a stub, and the stubs are filed in one long list from the lowest ticket number to the highest. Not every number was sold, so there are gaps.
The head teacher reads out a winning number. Before anyone walks up to the stage, you want to know if that ticket was actually sold, and where its stub sits in your list.
Your task
Write findTicket(tickets, drawn). tickets is sorted from smallest to largest and has no repeats. Return the index of drawn in tickets, or -1 if that number was never sold.
Use the sorted order: your solution should look at about log₂ n stubs, not all of them. An empty list returns -1.
findTicket(tickets: int[], drawn: int) → int
Examples
tickets = [102, 215, 340, 488, 519, 760, 901] drawn = 488
3
Look at the middle stub first: index 3 holds 488. That is the drawn number, so the answer is 3 after a single look.
tickets = [102, 215, 340, 488, 519, 760, 901] drawn = 500
-1
The middle stub is 488, which is less than 500, so 500 can only be to its right: 519, 760, 901. The middle of those is 760, too big, so look left of it: just 519. That is not 500 either, and nothing is left to check. Three looks, and 500 was never sold.
Constraints
- 0 ≤ tickets.length ≤ 100,000
- 1 ≤ tickets[i], drawn ≤ 1,000,000,000
- tickets is strictly increasing (sorted, no repeats).
Start with brute force
Read the stubs one by one from the start until you find the number or run out. That is correct and simple.
With 100,000 stubs it can take 100,000 looks for one call, and it ignores the most useful fact you have: the list is sorted. Binary search needs about 17 looks for the same list, because 2¹⁷ is more than 100,000.
Hints
0 of 4 shown- Hint 1
Take the first example and look only at the middle stub, 488. If the drawn number were 700, which half of the list could you throw away without reading it?
- Hint 2
One look at the middle rules out half of what is left, because the list is sorted. Keep the part that is still possible as a range from
lotohi. - Hint 3
Each round: look at the middle of the range. Equal means done. Too small means the answer is to the right, so move
lopast the middle. Too big means movehibefore it. When does the range become empty? - Hint 4
Start with
lo = 0andhi = n - 1. Loop whilelo <= hi(the=matters: a range of one stub still needs checking). Setmid = floor((lo + hi) / 2)and compare. If the loop ends, return-1.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
A sorted list lets one comparison rule out half the candidates. Keep a range [lo, hi] of positions where the number could still be, and halve it each round.
Trace [102, 215, 340, 488, 519, 760, 901] looking for 500:
lo = 0,hi = 6,mid = 3. 488 < 500, so everything at index 3 or lower is too small.lo = 4.lo = 4,hi = 6,mid = 5. 760 > 500, so index 5 and above are too big.hi = 4.lo = 4,hi = 4,mid = 4. 519 > 500.hi = 3.- Now
lo = 4is pasthi = 3. The range is empty, so return-1.
Notice step 3: the range held a single stub and still had to be checked. That is why the loop runs while lo <= hi, not lo < hi. With <, searching for 901 would stop before ever looking at the last stub.
Also notice the moves are mid + 1 and mid - 1, never just mid. You already checked mid, so leave it out. Keeping it can make the range stop shrinking and loop forever.
function findTicket(tickets, drawn) {
let lo = 0, hi = tickets.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (tickets[mid] === drawn) return mid;
if (tickets[mid] < drawn) lo = mid + 1; // answer is to the right
else hi = mid - 1; // answer is to the left
}
return -1; // the range is empty: never sold
}def find_ticket(tickets, drawn):
lo, hi = 0, len(tickets) - 1
while lo <= hi:
mid = (lo + hi) // 2
if tickets[mid] == drawn:
return mid
if tickets[mid] < drawn:
lo = mid + 1 # answer is to the right
else:
hi = mid - 1 # answer is to the left
return -1 # the range is empty: never soldRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.