33 - Search In Rotated Sorted Array

#medium

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        if ( target >= nums[left] && target <= nums[right] ) {
            while ( left <= right ) {
                int middle = ( left + right ) / 2;
                if( nums[middle] == target ) return middle;
                else if ( nums[middle] < target ) left = middle + 1;
                else right = middle - 1;
            }

        }
        else if ( target >= nums[left] ) {
            for ( int i = left; i < nums.size(); i++ ) {
                if ( nums[i] == target ) return i;
                else if ( nums[i] < nums[left] ) break;
            }

        }
        else {
            if ( target > nums[right] ) return -1;
            for ( int j = right; j < nums.size(); j-- ) {
                if ( nums[j] == target ) return j;
                else if ( j > 0 && nums[j-1] > nums[j] ) break;
            }

        }

        return -1;
    }
};

我們的二分查找的思想就是找出某個條件，這個條件給了我們移動左右指針的參考，即要判斷查找的target在mid的左邊還是右邊。具體到這個題目，因為給出的數組是旋轉有序的，如果mid指向的位置在於pivot之後，那麼mid向後部分是有序的，這個時候需要判斷target在mid左邊還是右邊，最簡單的方法就是判斷target是不是在[pivot,r]區間內，如果的話就向mid後半部分搜索，否則就向mid左半部分搜索；同理，當mid在pivot之前，那麼mid前面部分是有序的，根據target判斷下面要向mid的左邊還是右邊搜索。

（1）如果target = A[m]，那麼m就是我們要的結果，直接返回；
（2）如果A[m]<A[r]，那麼說明從m到r一定是有序的（沒有受到rotate的影響），那麼我們只需要判斷target是不是在m到r之間，如果是則把左邊緣移到m+1，否則就target在另一半，即把右邊緣移到m-1。
（3）如果A[m]>=A[r]，那麼說明從l到m一定是有序的，同樣只需要判斷target是否在這個範圍內，相應的移動邊緣即可。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while ( left <= right ) {
            int mid = left + ( right - left ) / 2;
            if ( nums[mid] == target ) return mid;
            // 在右半部嗎?
            if (  nums[mid] < nums[right] ) {
		            // 在右半部且右半有序的
                if ( target > nums[mid] && target <= nums[right] ) {
                    left = mid + 1;
                }
                // 不在右半部，重新尋找mid
                else {
                    right = mid - 1;
                }
            }
            else {
			          // 在左半部且左半是有序的
                if ( target >= nums[left] && target < nums[mid] ) {
                    right = mid - 1;
                }
                // 不在左半部，重新尋找mid
                else {
                    left = mid + 1;
                }
            }

        }

        return -1;
    }
};