354. Lowest on the Turned Shelf
A greenhouse records the temperature of every shelf as a row, sorted from coldest to warmest and all different. A caretaker spun the rack, so the row now starts somewhere in the middle of the sorted order, for example [40, 55, 70, 10, 25] instead of [10, 25, 40, 55, 70].
Given the turned array nums, return its smallest value. You do not know by how many places the rack was turned, and it may not have been turned at all. Solve it in O(log n) time: reading every temperature would be too slow when there are hundreds of thousands of shelves.
Example 1
- Input:
- nums = [11,13,15,17,5,7]
- Output:
- 5
- Explanation:
The array was turned so that 5 now sits after 17; 5 is the smallest value.
Example 2
- Input:
- nums = [4,9]
- Output:
- 4
- Explanation:
The array is not turned, so the first value, 4, is the smallest.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109
All values are distinct. nums is a sorted array rotated by an unknown amount (possibly zero).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)