Cheapest point on the curve: hints, no solution
Medium · Binary search
A capacity planner has priced a service at every instance size from 0 upward. The price list, indexed by size, always falls strictly from the first entry to some cheapest size and then rises strictly for every larger size. The cheapest size can be the first entry (prices only rise) or the last (prices only fall). No two neighbouring sizes have the same price, so the cheapest size is unique.
Return the size, as a zero-based index, with the lowest price. Reading every price is allowed, but the intended solution inspects only a logarithmic number of them.
Examples
- Input
- prices = [9, 6, 4, 5, 8]
- Output
- 2
- Note
- 4 is the lowest price and sits at index 2.
- Input
- prices = [3, 5, 9]
- Output
- 0
- Note
- A list that only rises has its cheapest size at index 0.
Constraints
- 1 <= prices.length <= 2500
- 1 <= prices[i] <= 100000
- Neighbouring prices differ, and the list falls and then rises
Hint 1: a nudge
Compare the price at some size with the price at the next size. What does that comparison say about which side of the cheapest size you are on?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.