描述

假設(shè)一個(gè)旋轉(zhuǎn)排序的數(shù)組其起始位置是未知的比如：（0 1 2 4 5 6 7 可能變成是4 5 6 7 0 1 2），你需要找到其中最小的元素。

注意事項(xiàng)

你可以假設(shè)數(shù)組中不存在重復(fù)的元素。

樣例

給出[4,5,6,7,0,1,2] 返回 0

思路

1. 找到一個(gè)分界點(diǎn)，以這個(gè)點(diǎn)為分界點(diǎn)將數(shù)組分為兩部分，第一部分值大于分割點(diǎn)，第二部分值小于分割點(diǎn)，最小值為第二段區(qū)間的第一個(gè)點(diǎn)，本題要以數(shù)組最后一個(gè)元素作為數(shù)組的分界點(diǎn)
2. 不能取第一個(gè)元素做分割點(diǎn)，當(dāng)數(shù)組是沒(méi)有旋轉(zhuǎn)情況下，比如數(shù)組為1、2、3時(shí)，取第一個(gè)點(diǎn)作為分割點(diǎn)時(shí)數(shù)組分為兩段分別是1和 2、3，程序返回第二段區(qū)間的第一個(gè)點(diǎn)是的是2，而正確結(jié)果應(yīng)該是1。但如果取的是最后一個(gè)點(diǎn) 3 做分割，第一部分沒(méi)有值，第二部分值為 1、2、3，則第二部分最小值為1，為最小值
3. 不斷二分最后鎖定在斷點(diǎn)兩端的兩個(gè)點(diǎn)上；但要考慮特殊情況比如正常的01234567順序，start 和 end 兩個(gè)點(diǎn)都小于 target，所以應(yīng)該先判斷 start 位置的元素

代碼

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0;
        int end = nums.length - 1;
        int target = nums[nums.length - 1];
        // target 即為將循環(huán)數(shù)組分為兩部分的數(shù)值分界點(diǎn)(一部分大于target，一部分小于target)
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            /* 根據(jù)if條件判斷mid是在循環(huán)數(shù)組的前面還是后面
             * 二分法會(huì)使得start和end最終返回在分界點(diǎn)，但
             * 到底是前面點(diǎn)還是后面點(diǎn)不確定，需要用if來(lái)檢驗(yàn)
             * 求最小值往前找總是沒(méi)錯(cuò)的
             */
            if (nums[mid] <= target) {
                end = mid;
            }
            if (nums[mid] > target) {
                start = mid;
            }
        }
 
        // nums[start] < target 說(shuō)明數(shù)組未旋轉(zhuǎn)
        // nums[end] = target 說(shuō)明數(shù)組值都是相同值
        if (nums[start] <= target) {
             return nums[start];
        }
        else {
            return nums[end];
        }
    }
}

最后這個(gè) double check 在特殊情況即 12345 這種未旋轉(zhuǎn)順序下可能出現(xiàn) start <= target 如果不考慮這種特殊情況，double check 可以直接寫(xiě)成 return nums[end]