Problem Statement
You have an array of length n
, which was initially sorted in ascending order. This array was then rotated x
times. It is given that 1 <= x
<= n. For example, if you rotate [1, 2, 3, 4]
array 3
times, resultant array is [2, 3, 4, 1]
.
Your task is to find the minimum element from this array. Note that the array contains unique elements.
You must write an algorithm that runs in O(log n)
time.
Example 1:
 Input: [8, 1, 3, 4, 5]
 Expected Output: 1
 Justification: The smallest number in the array is 1.
Example 2:
 Input: [4, 5, 7, 8, 0, 2, 3]
 Expected Output: 0
 Justification: The smallest number in the array is 0.
Example 3:
 Input: [7, 9, 12, 3, 4, 5]
 Expected Output: 3
 Justification: In this rotated array, the smallest number present is 3.
Solution
To determine the minimum element in a rotated sorted array, we'll leverage the binary search method.
In a standard sorted array, the elements increase (or remain the same) from left to right. But in our rotated sorted array, at some point, there will be a sudden drop, which indicates the start of the original sorted sequence and, hence, the minimum element. This drop will be our guide during the search. With binary search, we'll repeatedly halve our search range until we pinpoint the location of this sudden drop or the smallest element.

Initialization: Start with two pointers,
left
andright
, set at the beginning and the end of the array, respectively. 
Binary Search Process:
 Calculate the middle index,
mid
.  If the element at
mid
is greater than the element atright
, this indicates that the minimum element is somewhere to the right ofmid
. Hence, updateleft
tomid + 1
.  Otherwise, the minimum element is to the left, so update
right
tomid
.
 Calculate the middle index,

Termination: The loop will eventually lead
left
to point to the minimum element. This happens whenleft
equalsright
. 
Edge Case Handling: If the array isn't rotated at all, the smallest element will be the first. Our binary search process accounts for this scenario.
Algorithm Walkthrough
Consider the array [4, 5, 7, 8, 0, 2, 3]:
 Start with
left
= 0 andright
= 6.  Calculate
mid
= (0 + 6) / 2 = 3. The array element at index 3 is 8.  Since 8 > 3 (element at
right
), updateleft
tomid + 1
= 4.  Now,
left
= 4 andright
= 6. Calculatemid
= (4 + 6) / 2 = 5.  Element at index 5 is 2. Since 2 < 3, update
right
tomid
= 5.  Now,
left
= 4 andright
= 5. Calculatemid
= (4 + 5) / 2 = 4.  Element at index 4 is 0. Since 0 < 2, update
right
tomid
= 4. left
is now equal toright
, both pointing at index 4, where the minimum element 0 is present.
Code
Complexity Analysis
Time Complexity: O(log n) because we are using a binary search approach, which reduces the problem size by half in each step.
Space Complexity: O(1) as we are using a constant amount of space regardless of the input size.