L153 Find Minimum in Rotated Sorted Array

Binary Search

Problem:

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]    45123
Output: 1

Solution:

• 2 conditions:

  • array[left] < array[mid]: t, that we are in the bigger part, so the the mini is in our right, so move to the right.( left = mid)

  • else , we are in the smaller part, so go left(right = mid)

public int findMinimum(int[] array){
    if(array == null || array.length == 0) return -1;
    if(array.length == 1) return array[0];
    int left = 0, right = array.length - 1;
    if(array[left] < array[right]) return array[left];
    while(left + 1 < right){
        int mid = left + (right - left) /2;
        if(array[mid] > array[left]){
            left = mid;
        }else{
            right = mid;
        }
    }
    return array[right] < array[left] ? array[right] : array[left];
}