# 153 Find Minimum in Rotated Sorted Array – Medium

### Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

### Thoughts:

Using a O(n) iteration to find the min value in the array is too trivial and straight forward. So it is already clear enough that a Binary Search is needed here.

So this is a problem of modified Binary Search.

### Solutions:

``````public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length ==0) {
return -1;
}
if (nums <= nums[nums.length - 1]) {
return nums;
}
return bs(nums, 0, nums.length - 1);
}
private int bs(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
}
int mid = (start + end) / 2;
if (mid > 0 && nums[mid -1] > nums[mid]) {
return nums[mid];
}
if (nums[mid] >= nums) {
return bs(nums, mid + 1, end);
}
else {
return bs(nums, start, mid - 1);
}

}
}
``````

non-Recursion:

``````public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}

int start = 0, end = nums.length - 1;
int target = nums[nums.length - 1];

// find the first element <= target
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] <= target) {
return nums[start];
} else {
return nums[end];
}
}
}
``````