The problem
A station lists its platform numbers from smallest to largest, with no repeats. You are given this list, platforms, and a platform number, target. Return the index where target is in the list. If it is not in the list, return -1.
search([3, 7, 11, 14, 19], 14) # 3
search([3, 7, 11, 14, 19], 12) # -1
search([], 5) # -1
In the large tests, the list counts every value you read from it. A binary search stays well under the limit. Anything that goes through the whole list goes over it. This includes in, .index(), list(…), sorted(…) and slicing.
Limits
- Up to 1,000,000 platforms. At most 25 reads on the large tests.
- The list may be empty.
Builds on BSRC-1 Halving the search space and BSRC-2 The invariant.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Target in the middle | Not run | |
| 2 | Target at index 0 | Not run | |
| 3 | Target at the last index | Not run | |
| 4 | Not in the list, smaller than all values | Not run | |
| 5 | Not in the list, bigger than all values | Not run | |
| 6 | Not in the list, between two values | Not run | |
| 7 | Empty list | Not run | |
| 8 | One platform, present | Not run | |
| 9 | One platform, not in the list | Not run | |
| 10 | Two platforms | Not run | |
| 11 | A million platforms, at most 25 reads | Not run | |
| 12 | A million platforms, target not in the list | Not run |