LeetCode 81. Search in Rotated Sorted Array II [Medium] [C++] 解題筆記

這題是 33. Search in Rotated Sorted Array 的 follow up，一樣給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，但 array 中的數字可能重複，要求我們在此 array 中搜索特定數字。

EX:

        nums = [1,1,3,1],  target = 3 

    

        

Ans: true

想法:

            這題基本上與上一題相當類似，但差別在於可能出現重複數字，如果沒有重複數字的話，我可以依照"中間的數大於最右邊的數" 和 "中間的數小於最左邊的數" 來得知 left ~ mid 或 mid ~ right 是排序好的，然後採用 binary search 來踢掉不必要的區間。但有重複數字的話會發現這個判斷標準失效了，如同上面的例子，因為有重複數字所以即使中間數字小於等於最右邊的數字也不代表 mid ~ right 是遞增的，所以我們必須排除相同數字的影響，如果最右邊的數字和中間的數字是相同的話就比較前一個數字 ( right-- )，直到比到與 mid 不相同的 right，如此即可確保 mid ~ right 或是 left ~ mid 是有序的。

Complexity: O(logn) time, O(1) space.

完整程式碼:

class Solution {

public:

    bool 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 true;

            }

            // which means that mid ~ right is sorted

            if (nums[mid] < nums[right]) {

                //target is in this range

                if (nums[mid] < target && target <= nums[right]) {

                    left = mid + 1;

                }

                else {

                    right = mid - 1;

                }

            }

            // which means that left ~ mid is sorted

            else if (nums[mid] > nums[right]) {

                // target is in this range

                if (nums[mid] > target && target >= nums[left]) {

                    right = mid - 1;

                }

                else {

                    left = mid + 1; 

                }

            }

    // avoid duplicate

            else {

                right--;

            }

        }

        return false;

    }

};