# Short and Simple log(n) Solution

• ``````   public static int findMin(int[] num) {
return findMin(num, 0, num.length-1);
}
public static int findMin(int[] num, int start, int end) {
if(end-start<=1) return Math.min(num[start],num[end]);
int middle = (start+end)/2;
if(num[start]<num[middle]) return (num[middle]<=num[end]) ? num[start] : findMin(num,middle,end);
else if(num[start]==num[middle]) return (num[middle]==num[end]) ? Math.min(findMin(num,start,middle), findMin(num,middle,end)) :findMin(num,middle,end);
else return (num[middle]<=num[end]) ? findMin(num,start,middle) : -1;
}
``````

The minimum will be at the rotation point.

We need to take into account at each step num[start], num[middle], num[end] to find the rotation point, if it exist. The array can have just one point breaking the increasing trend.

Let consider all the possible 9 cases:

1. num[start] < num[middle] < num[end] => min=num[start]
2. num[start] < num[middle] = num[end] => min=num[start]
3. num[start] < num[middle] > num[end] => min between middle and end
4. num[start] = num[middle] < num[end] => min between middle and end
5. num[start] = num[middle] = num[end] => min could be everywhere, search recursively left and right and return the min between the two searches
6. num[start] = num[middle] > num[end] => min between middle and end
7. num[start] > num[middle] < num[end] => min between start and middle
8. num[start] > num[middle] = num[end] => min between start and middle
9. num[start] > num[middle] > num[end] => IMPOSSIBLE (array should have at least 2 rotation points)

• if these numbers are all the same, i think your algorithm will be O(n).

• You cannot distinguish an array of 1's from an array of 1's and one 0 unless you read all the elements of the array. This is true since the 0 could be placed anywhere and the array will still be sorted. Therefore, the best you can do is O(n) which is trivial. This is a trick question.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.