資料結構與算法:旋轉數組的最小數字

public class MinNumberInRotateArraySearch {

    public int minNumberInRotateArray(int [] array) {

        int left = 0;
        int right = array.length-1;
        
        /*
        * 我的思路有問題: 用中間數mid和中間數的右邊數mid+1比較，這樣沒有什麼意義
        * */
        while(left<right){
            int mid = left +(right-left)/2;
            if(array[mid]<=array[mid+1] && array[mid] <= array[0]){
                right = mid;
            }else if(array[mid]<=array[mid+1] && array[mid] > array[0]){
                left = mid+1;
            }else if(array[mid] > array[mid+1]){
                return array[mid+1];
            }else{
                // 相等
                right = mid;
            }
        }

        return 0;
    }

    public int minNumberInRotateArray2(int [] array) {
        // 如果數組無元素，那麼傳回0
        if (array.length <= 0)
            return 0;
        // 定義左邊界
        int left = 0;
        // 定義有邊界-----在二分查找中，左邊界值一定小于或等于右邊界值
        int right = array.length - 1;
        while (left <= right){
            // 計算左右區間最中間的索引
            int mid = left + ((right - left)>>1);
            // 如果中間的值小于右邊的值，說明此時數組最小值在左半部，
            // 挪動右邊界指針到中間索引，為了避免此時的中間索引值就是最小的值，是以mid不能夠減1
            if (array[mid] < array[right]) {
                right = mid;
            }
            // 如果中間的值大于的值，說明此時的最小值在右半部，挪動左邊界指針到目前中間索引的後一個
            else if (array[mid] > array[right]) {
                left = mid + 1;
            }
            // 如果中間值與右邊界值相同，那麼挪動右邊界向左靠一位，這樣就可以在下次循環時重新計算出中間索引值
            else right--;  // 形成新的邊界
        }
        // 左邊界永遠小于或等于右邊界，那麼就直接傳回左邊界所對應的數組值
        return array[left];
    }

    public static void main(String[] args) {

    }
}