A hotel keeps booking numbers in a list sorted from smallest to largest, with no duplicates. Write a function that returns the index of target in the list, or -1 if it isn't there. Your solution should take O(log n) time, so don't scan the whole list.
Write find_booking(bookings, target) in Python or findBooking(bookings, target) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Use the order
In a sorted list, one comparison with the middle item tells you which half the target must be in. Throw away the other half.
Step 2
Keep a range that must contain the target
Track low and high such that, if the target is in the list at all, it's between them (inclusive). Start with the whole list: low = 0, high = len - 1.
Step 3
Shrink the range correctly
Compare the middle item. If it's too small, the target is to its right: low = mid + 1. If it's too big: high = mid - 1. The + 1 and - 1 matter: mid itself has been ruled out, and leaving it in can loop forever.
Step 4
When to stop
Loop while low <= high. When the range is empty (low > high), the target isn't there.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Binary search with an inclusive range [low, high]. Return mid on a match; otherwise move low or high past mid. Return -1 when the range runs out.
python
1def find_booking(bookings, target):
2 low, high = 0, len(bookings) - 1 # if target is here, it's in bookings[low..high]
↑the target, if here, is in [low, high]
3 while low <= high:
↑stop when the range is empty
4 mid = (low + high) // 2
5 if bookings[mid] == target:
6 return mid
7 if bookings[mid] < target:
8 low = mid + 1
↑mid is ruled out
9 else:
10 high = mid - 1
↑mid is ruled out
11 return -1
javascript
1function findBooking(bookings, target) {
2 let low = 0
3 let high = bookings.length - 1 // if target is here, it's in bookings[low..high]
↑the target, if here, is in [low, high]
4 while (low <= high) {
↑stop when the range is empty
5 const mid = Math.floor((low + high) / 2)
6 if (bookings[mid] === target) return mid
7 if (bookings[mid] < target) low = mid + 1
↑mid is ruled out
8 else high = mid - 1
↑mid is ruled out
9 }
10 return -1
11}
Complexity
TimeO(log n)SpaceO(1)
O(log n) time and O(1) extra space.
What we learned
Binary search needs sorted data and a range you know contains the answer.
Rule out mid after checking it (mid + 1, mid - 1), and loop while the range isn't empty.
In Python, bisect.bisect_left does the same search; say you'd use it in real code, but know how to write it.