2.4 Find Minimum in Rotated Sorted Array

Look for min number in rotated sorted array.

Example

Given [4, 5, 6, 7, 0, 1, 2] return 0

Logical Steps

1. Rotated sorted array has left and right parts, if mid at left part, move to right; if mid at right part, move to left;
2. Get start and end eventually, pick the smaller number

Code Template

    public int findMin(int[] num) {
        int start = 0;
        int end = num.length-1;

        while(start + 1< end) {
            int mid = (start+end) / 2;

            /** in rotated array, there are two parts
             * left part: everything > num[0]
             * right part: everything < num[end]
             * if mid in first part, move to right
             * if mid in right part, move to left
             * min is at first element of right part
             */
            if (num[mid] > num[end]) {
                start = mid;
            }else{
                end = mid;
            }
        }

        // when we get start and end, pick the smaller one
        if (num[start] > num[end]) {
            return num[end];
        }else{
            return num[start];
        }
    }