Leetcode 153 Find Minimum in Rotated Sorted Array.

This problem is really weird, cause you can use a very simple way to figure it out. The runtime difference is very little.

Problem 153 Find Minimum in Rotated Sorted Array

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.

``````public class Solution {
public int findMin(int[] nums) {
Arrays.sort(nums);
return nums;
}
}
``````

Looks like it gonna run out of time? Nope. So looks like it is working.

But I still want to find a normal way for this problem.

And I find divide and conquer.

``````public class Solution {
public int findMin(int[] num) {
return findMin(num, 0, num.length - 1);
}

public int findMin(int[] num, int left, int right) {
if (left == right)
return num[left];
if ((right - left) == 1)
return Math.min(num[left], num[right]);

int middle = left + (right - left) / 2;

// not rotated
if (num[left] < num[right]) {
return num[left];

// go right side
} else if (num[middle] > num[left]) {
return findMin(num, middle, right);

// go left side
} else {
return findMin(num, left, middle);
}
}
}
``````