LeetCode---81. Search in Rotated Sorted Array II

##LeetCode—81. Search in Rotated Sorted Array II

####題目

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/

給出一個升序排列的數組，注意是非嚴格升序，可以有重複元素，然後數組旋轉，得到将要操作的數組(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).，給出一個整數，判斷該數是否存在于數組中，若是，傳回true，否則false。例子：

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
           

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
           

####思路及解法

這道題是33.Search in Rotated Sorted Array的更新版。在33那道題裡我們的思路是先根據nums[left]和nums[mid]的大小關系判斷那邊有序，然後判斷target是否在有序的那邊，如果是，則在有序的一邊尋找，否則在另一邊尋找，這樣實作了logN的時間複雜度。但是這道題的數組裡的元素可以是重複的，也即是nums[left]和nums[mid]有可能是相等的，例如假設原數組是{1,2,3,3,3,3,3}，那麼旋轉之後有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，這樣的我們判斷左邊緣和中心的時候都是3，如果我們要尋找1或者2，我們并不知道應該跳向哪一半。這樣就會導緻我們有可能不能判斷左右兩側到底那邊是有序的，也就無法獲知應該從那邊開始尋找，是以我們要針對相等的情況單獨讨論，在這種情況下，想到的方法是left++,直到可以判斷出大小，否則一直循環到結束。時間複雜度On。

33題的關鍵思路是，不管怎們樣，我們一定能找到一個有序的一側，而另一側是混序的，也就是二分的話，一定是一個升序序列+一個混序序列。再根據target是否在有序一側來二分序列，就是如果在有序一側那麼就在裡面進行二分查找，否則的話就吧混序一側當成一個形式相同的原序列。

這道題的真正差別不是造成了非嚴格升序的問題，而是二分序列的時候會形成三種序列：混序，升序，平序（就是數相等）。這樣在用33題的方法時，就有一個問題：兩側的序列有可能都不是升序序列，額可能是混序+平序。以左側序列為例。如果左側為升序，我們先在看target是否落在左側内，如果是，直接在左側二分查找，如果不是，則需要在右側進行查找。如果左側是混序，我們去看target是否落在右側，如果是，進入右側，如果不是進入左側。如果是平序，讓left++。

####代碼

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int mid = 0;
        int right = nums.length - 1;
        while(left <= right){
            mid = (left+right)/2;
            if(target == nums[mid])
                return true;
            if(nums[left] < nums[mid]){//左側升序
                if(target<nums[mid] && target>=nums[left])
                    right = mid - 1;
                else
                    left = mid + 1;
            }else if(nums[left] > nums[mid]){
                if(target>nums[mid] && target<=nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }else{
                left++;
            }
        }
        return false;
    }
}