The worst situation O(N).
Actually we can either just loop through, or we can compare num[mid] with the num[end], if they are the same, that means it‘s fine to remove end, the smallest element won‘t be removed
public class Solution { /** * @param num: a rotated sorted array * @return: the minimum number in the array */ public int findMin(int[] num) { // write your code here if (num == null || num.length == 0) { return -1; } int start = 0; int end = num.length - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; // we want to keep the lower part, so use endVal to compare if (num[mid] == num[end]) { end--; } else if (num[mid] < num[end]) { end = mid; } else { start = mid; } } if (num[start] <= num[end]) { return num[start]; } if (num[end] < num[start]) { return num[end]; } return -1; } }
Find Minimum in Rotated Sorted Array II
原文:http://www.cnblogs.com/codingEskimo/p/6805093.html