376. Floor on the Shelf
A price board lists the sizes of the shirts a shop stocks, sorted from smallest to largest, and repeated sizes are allowed. A customer asks for a shirt of size target, but if the shop does not have that exact size they will take the biggest size that is not larger than they asked for.
Given the sorted array nums of sizes (all at least 0) and an integer target, return the largest value in nums that is less than or equal to target, or -1 if every size is larger than target. Your solution should use O(log n) time.
Example 1
- Input:
- nums = [2,6,10,14], target = 11
- Output:
- 10
- Explanation:
The sizes not larger than 11 are 2, 6 and 10, and the biggest is 10.
Example 2
- Input:
- nums = [2,6,10,14], target = 1
- Output:
- -1
- Explanation:
Every size is larger than 1, so the answer is -1.
Constraints
1 ≤ nums.length ≤ 106
0 ≤ nums[i] ≤ 109
0 ≤ target ≤ 109nums is sorted in non-decreasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)