題目描述

LeetCode 33題
假設(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) 級(jí)別。

示例

示例 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í)間復(fù)雜度要求是O(log n)，應(yīng)該是使用二分查找。盡管數(shù)組整體無(wú)序，但是部分有序。所以我們可以將數(shù)組二分，逐步縮小搜索區(qū)域。每次迭代都從有序部分入手，如果target在有序部分的數(shù)組之內(nèi)，那么正中我們的下懷，如果target不在有序部分的數(shù)組之內(nèi)，則將搜索范圍縮小至無(wú)序部分，繼續(xù)進(jìn)行二分，直到left>right。

代碼實(shí)現(xiàn)（c++）

int search(vector<int>& nums, int target) {
        int n=nums.size();
        if (n==0)
            return -1;
        if (n==1 && target == nums[0] )
            return 0;
        else if (n==1 && target != nums[0])
            return -1;
        int left=0;
        int right=n-1 ;
        while(left<=right){
            int mid = left + (right - left)/2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[0] <= nums[mid]){
                if (nums[0] <= target && target < nums[mid]){
                    right = mid - 1;
                }
                else{
                    left = mid +1;
            }
            }
            else{
                if (nums[mid] < target && target <= nums[n-1]){
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
             
        }
        return -1;
        
    }