Find Minimum in Rotated Sorted Array

Suppose you have given an array sorted in ascending order. The array is rotated at some unknown pivot point. Following the example of a sorted rotated array.

``[0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]``

Find the minimum element from the array. You may assume no duplicate exists in the array.

Example 1:

```Input: [8,9,10,1,2,4]
Output: 1
```

Example 2:

```Input: [4,5,6,7,0,1,2]
Output: 0```

The brute force approach to solve this problem is to search the entire array and find the minimum element. The time complexity for that would be `O(N)` given that `N` is the size of the array. But we can do better with the `Binary Search` algorithm. `Binary Search` can solve the problem in `O(logN)` time. Since the given array is sorted, we can make use of Binary Search. However, the array is rotated. So simply applying the binary search won’t work here. So we can use a slightly modified version of `Binary Search` to solve the problem. So there are 2 conditions to apply with the modified version of Binary Search.

If the array is not rotated then `A[0]` is the smallest element of the sorted array. How to find if the array is not rotated?  Simple `last element of the array > first element`.

Otherwise, calculate the `mid` of the array by `left + (right-left)/2`. Until you find `A[mid] > A[mid+1]`.

Once you find `A[mid] > A[mid+1]` then `A[mid+1]` is the smallest element of the array.

Following is the Java Implementation:

```class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
if (nums.length == 1) return nums[0];
int left = 0, right = (nums.length - 1);
if (nums[left] <= nums[right]) return nums[left];
while (left < right) {
int pivot = left + (right - left) / 2;
if (nums[pivot] > nums[pivot + 1]) return nums[pivot + 1];
if (nums[pivot] > nums[left]) left = (pivot + 1);
else right = pivot;
}
return -1;
}
}
```

Complexity Analysis

• Time Complexity: Same as Binary Search `O(logN)`
• Space Complexity: `O(1)`

Categories: Binary Search