Find Minimum in Rotated Sorted Array

Problem

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

Example 1:

Input: [3,4,5,1,2] 

Output: 1

Example 2:

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

Output: 0

Solution

This is an edge detection problem, the brutal force way is to check the first occurrence of a[i-1] > a[i]. The time cost will be O(N).

With binary search, the cost can be cut down to O(logN). The middle could land on the left of the edge or right of the edge. We also need to consider special cases when the array is not rotating, the array has only one element. 

public class MinInRotatedArray {
  public static int min(int[] a) {
    //3,4,5,6,7,0,1,2
    //        * .   
    int N = a.length;//8
    int lo = 0;
    int hi = N - 1;
    if(a[lo] <= a[hi]) return a[lo];
   
    int mid = 0;
    while(lo < hi) {//4,7
      mid = lo + (hi - lo)/2;//5
      if(mid > 0 && a[mid] < a[mid - 1]) {
        return a[mid];
      } else if(mid < N - 1 && a[mid] > a[mid+1]) {
        return a[mid+1];
      }
      if(a[lo] < a[mid]) lo = mid + 1;
      else if(a[lo] > a[mid]) {
        hi = mid - 1;
      }
      else return a[mid];
    }
    return a[mid];
  }
  public static void main(String...args) {
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{5,6,7,0,1,2,3,4}));
    System.out.println(min(new int[]{0,1,2,3,4,5,6,7}));
    System.out.println(min(new int[]{7,0,1,2,3,4,5,6}));
    System.out.println(min(new int[]{1,2,3,4,5,6,7,0}));
    System.out.println(min(new int[]{0}));
  }
}

Time cost O(logN), space cost O(1).