一、旋轉(zhuǎn)數(shù)組中的最小數(shù)字

題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉(zhuǎn)，該數(shù)組的最小元素為1。

解法一：順序查找，復雜度O(n)

var search = function(nums){
    var min = nums[0];
    for(var i=1;i<nums.length;i++){
        if(nums[i]<=min){
            min = nums[i];
        }
    }
    return min;
}

解法二：二分查找，復雜度O(logn)

var search = function(nums){
    var left = 0,
    right = nums.length-1,
    mid = 0;
    while(right-left > 1 && nums[right] <= nums[left]){
         mid = parseInt((left+right)/2);
         // 左區(qū)間是遞增序列，最小元素在右區(qū)間
         if(nums[left]<=nums[mid]){
             left = mid;
         }
         // 右區(qū)間是遞增序列，最小元素在左區(qū)間
         if(nums[mid]<=nums[right]){
             right = mid;
         }
     }
    return nums[right];
}

二、搜索旋轉(zhuǎn)數(shù)組中的元素

題目：在旋轉(zhuǎn)數(shù)組中搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。假定數(shù)組中沒有重復元素。

思路：二分查找，復雜度O(logn)

參考https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-bai-liao-9983de-javayong-hu-by-reedfan/

取區(qū)間的中間值mid后：

1. 如果nums[mid] == target，直接返回mid值；
2. 如果nums[mid] >= nums[left]，說明左半?yún)^(qū)間是遞增序列；如果target落在左半?yún)^(qū)間，則在左半?yún)^(qū)間內(nèi)搜索，否則在右半?yún)^(qū)間內(nèi)搜索
3. 如果nums[mid] <= nums[left]，說明右半?yún)^(qū)間是遞增序列；如果target落在右半?yún)^(qū)間，則在右半?yún)^(qū)間內(nèi)搜索，否則在左半?yún)^(qū)間內(nèi)搜索

var search = function(nums,target){
    var left = 0,
        right = nums.length-1,
        mid = 0;
    if(nums.length == 0) return -1;
    while(right >= left){
        mid = parseInt((left+right)/2);
        if(nums[mid] == target) return mid;
        // 左半?yún)^(qū)間是遞增序列
        if(nums[left] <= nums[mid]){
            if(nums[left] <= target && target < nums[mid]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }else{ //右半?yún)^(qū)間是遞增序列
            if(nums[mid] < target && target <= nums[right]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
    }
    return -1;
}

三、搜索旋轉(zhuǎn)數(shù)組中的元素

題目：在旋轉(zhuǎn)數(shù)組中搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回true，否則返回false。數(shù)組中可能存在重復元素。

思路：二分查找，復雜度O(logn)

思路基本同上題，只是要考慮到[1,0,1,1,1] 和 [1,1,1,0,1]的情況：

1. 如果nums[mid] == target，直接返回mid值；
2. 如果nums[left] == nums[mid]，無法判斷遞增區(qū)間的位置，則需要將left++，去掉干擾元素；
3. 如果nums[mid] >= nums[left]，說明左半?yún)^(qū)間是遞增序列；如果target落在左半?yún)^(qū)間，則在左半?yún)^(qū)間內(nèi)搜索，否則在右半?yún)^(qū)間內(nèi)搜索
4. 如果nums[mid] <= nums[left]，說明右半?yún)^(qū)間是遞增序列；如果target落在右半?yún)^(qū)間，則在右半?yún)^(qū)間內(nèi)搜索，否則在左半?yún)^(qū)間內(nèi)搜索

var search = function(nums, target) {
    var left = 0,
    right = nums.length-1,
    mid = 0;
    if(nums.length == 0) return false;
    while(right >= left){
        mid = parseInt((left+right)/2);
        if(nums[mid] == target) return true;
        // 去掉重復項的干擾
        if(nums[left] == nums[mid]){
            left++;
            continue;
        }

        if(nums[left] <= nums[mid]){
            if(nums[left] <= target && target < nums[mid]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }else{
            if(nums[mid] < target && target <= nums[right]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
    }
    return false;
};