L154 Find Minimum in Rotated Sorted Array II

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.

The array may contain duplicates.

Example 2:

Input: [2,2,2,0,1]
Output: 0

Solution:

• first check the array is rotated or not;

• then, since the array may contain duplicates, so left++ or right-- to remove it;

• the check we are in the bigger part or smaller part;

public int findMini(int[] array){
    if(array == null || array.length == 0) return -1;
    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++;
        }else if(array[mid] == array[right]){
            right--;
        }else if(array[left] < array[mid]){
            left = mid;
        }else{
            right = mid;
        }
    }
    return Math.min(array[left], array[right]);
}