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

這題給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，且 array 中的數字不重複，要求我們在此 array 中搜索特定數字。

EX:

    nums = [4,5,6,7,0,1,2], target = 0

Ans: 4

想法:

        在排序好的 array 中搜索數字通常都會使用 binary search，因為已經排序好的所以用 binary search 可以輕鬆達到 O(logn) 的複雜度，但這題比較不一樣的是它不是從頭開始排序。因為採用 binary search 數列必須是有序的才能保證其正確性，首先我們注意到不管從哪個 index 開始排序，只要中間的數小於最右邊的數則表示右半邊的數列是有序的，而若中間的數大於最右邊的數則表示左半邊是有序的，我們只需要每次都在有序的那半邊裡面做搜索就可以採用 binary search 了！

0       1　　2　　 4　　5　　6　　 7

7　　0　　1　　 2　　4　　5　　 6

6　　7　　0　　 1　　2　　4　　 5

5　　6　　7　　 0　　1　　2　　 4

4　　5　　6　　 7　　0　　1　　 2

2　　4　　5　　 6　　7　　0　　 1

1　　2　　4　　 5　　6　　7　　 0

Time Complexity: O(logn)

完整程式碼:

class Solution {

public:

    int search(vector<int>& nums, int target) {

        int left = 0;

        int right = nums.size() - 1;

        

        while (left <= right) {

            // avoid overflow

            int mid = left + (right - left) / 2;

            if (nums[mid] == target) { return mid; }

            // which means that mid ~ right is sorted

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

                // target is in this range

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

                    left = mid + 1;

                }

                else {

                    right = mid - 1;

                }

            }

            // which means that left ~ mid is sorted

            else {

               // target is in this range

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

                    right = mid - 1;

                }

                else {

                    left = mid + 1; 

                }

            }

        }

        return -1; 

    }

};