LeetCode OJ (33)

這個題是將一個排序數組部分扭轉一下，導致數組成為部分有序的兩部分，現在給定一個target，最後找出該target的下標，若不存在則返回-1，題目意思還是很好理解的，但是求解的時候確實比較麻煩的。為什麼麻煩呢？因為遍歷一遍數組的方法並不適用，而且這樣的做法也沒有意義！

所以我們得另外開辟路徑，我們平時在查找有序數組的時候用的最多的方法是二分查找法，那麼這個題能否使用二分查找呢？答案是可以，而且就是用這種方法來查找target的下標的。思路如下：

雖然數組被扭轉了，並不是整個有序的，但是它還是部分有序的，舉個例子吧：如：”4 5 6 7 0 1 2“，我們可以看到數組的前後兩個部分還是有序的，我們可以利用這一點來求解，說道這裡我覺得不用再多多解釋了吧，直接看代碼吧：

class Solution {
public:
    int search(vector& nums, int target)
    { //這個題是給一個排序數組，但是數組裡面內容被平行移動了，如上例所示，現在要找到tagert所對應的下標
        int len = nums.size();
        
        //特殊情況先考慮掉
        if(len == 0)
        { return -1; }
        if(len == 1 && target!=nums[0])
        { return -1; }
        
        //正常情況，應該不能遍歷一邊數組吧，這樣沒有意義，應該也無法通過；雖然順序被打亂了，但是部分還是有序的，我們還是使用二分查找
        int left = 0;
        int right = len-1;
        int mid = 0;
        while(left <= right)
        {
            mid = left + (right-left)/2;
            
            if(target == nums[left])
            {
                return left;
            }
            if(target == nums[right])
            {
                return right;
            }
            if(target == nums[mid])
            {
                return mid;
            }
            
            //二分查找
            if(nums[mid] >= nums[left])
            {//左邊有序
                if(target > nums[left] && target < nums[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {//右邊有序
                if(target > nums[mid] && target < nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};