題目描述

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時(shí)間復(fù)雜度必須是 O(log n)級別。
相關(guān)話題：?數(shù)組、二分查找????難度：?中等

示例1
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出:4

示例2
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1

思路：
做有序數(shù)組的二分查找時(shí)，定義兩個(gè)指針l和r，

• 初始狀態(tài)，l = 0，r = nums.length - 1，在l <= r的條件下做循環(huán)，每次折掉一半數(shù)據(jù)；
• 每次循環(huán)算出l和r范圍內(nèi)中間的位置mid = l + ((r - l) >> 1)，
  1.如果目標(biāo)值target == nums[mid]，直接返回；
  2.如果target > nums[mid]那target肯定在mid的右邊(更新l,l = mid + 1)，否則在左邊(更新r,r = mid - 1)。

而我們這題的數(shù)組有可能發(fā)生了旋轉(zhuǎn)，那么就不能單純依據(jù)target和nums[mid]的比較來判斷target在mid的左還是在右。

• 左右部分有無序，分為三種情況:1.左無序，右肯定有序 2.右無序，左肯定有序 3.左右都有序，而判斷無序的條件是最左邊元素 > 最右邊元素
• 如果左邊有序，那么就通過判斷target是否落在左邊來判斷target在左還是在右；如果右邊有序，那么就通過判斷target是否落在右邊來判斷target在左還是在右；反正，誰有序就用誰來判斷，因?yàn)榕袛鄺l件是最左邊元素 < target < 最右邊元素。

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] == target){
                return mid;
            }
            //左部分無序，右部分有序
            if(nums[l] > nums[mid]){
                if(target >= nums[mid] && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
                //右部分無序，左部分有序
            }else if(nums[mid] > nums[r]){
                if(target <= nums[mid] && target >= nums[l]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
                //左右部分都有序
            }else{
                if(target <= nums[mid] && target >= nums[l]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
}

這里的mid也納入了左或右部分，而不是左：l->mid-1，右：mid+1->r。這是為了減少邊界的處理。
以下代碼：左：l->mid-1，右：mid+1->r

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] == target){
                return mid;
            }
            //左部分無序，右部分有序
            if(mid - 1 >= l && nums[l] > nums[mid - 1]){
                if(mid + 1 <= r && target >= nums[mid + 1] && target <= nums[r]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
                //右部分無序，左部分有序
            }else if(mid + 1 <= r && nums[mid + 1] > nums[r]){
                if(mid - 1 >= l && target <= nums[mid - 1] && target >= nums[l]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
                //左右部分都有序
            }else{
                if(mid - 1 >= l && target <= nums[mid - 1] && target >= nums[l]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
}

由于判斷條件使用到mid - 1和mid + 1的操作，可能會導(dǎo)致數(shù)組越界。