Min in Rotated Sorted Array | Dataford Interview Questions

PlanGrid can represent ordered construction data such as sorted sheet or revision identifiers. Given a sorted array that has been rotated at an unknown index, return its minimum element without sorting the array.

Assume all values are distinct and the original array was sorted in strictly increasing order. A rotation moves a suffix of the array to its beginning. For example, rotating [1, 2, 3, 4, 5] after index 2 produces [4, 5, 1, 2, 3].

Formal Specification

Implement find_min(nums), where nums is a non-empty list of integers. Return the smallest integer in nums.

Your solution must run in O(log n) time and use O(1) additional space.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
All values in nums are distinct
nums was formed by rotating a strictly increasing sorted array

Function Signature

def find_min(nums):

Your question is Min in Rotated Sorted Array. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem