33. Search in Rotated Sorted Array - Medium

前往題目

想法

• 之前寫過，條件實在不好想

思路

1. Binary search整個nums
2. 如果mid不是答案，看左指針的值是否小於等於mid的值，代表順序正常，再接著判斷，是否左邊的portion被rotate到右邊了
3. 如果都不是那判斷右邊portion是否被rotate到左邊去了，並移動指針

這次第二次做，覺得可以思考的方向是: mid和l指針的值正常的情況(l <= mid)如何判斷要移動哪個指針，而遇到不正常(l > mid)該怎麼判斷

Code

class Solution {
    public int search(int[] nums, int target) {
        
        int l = 0, r = nums.length - 1;
        // Binary search
        while (l <= r) {
            int mid = l + (r - l) / 2;

            // Found the ans
            if (nums[mid] == target)
                return mid;

            // 遇到正常排序
            if (nums[l] <= nums[mid]) {
                if (target > nums[mid] || // 檢查是否大於mid
                    target < nums[l]) { // 檢查是否小於l(這樣的話就一定在右邊，因為左邊被交換過去右邊了)
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else { // 不正常排序
                if (target < nums[mid] || // 檢查是否小於mid
                    target > nums[r]) { // 檢查是否大於r
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }

        return -1;
    }
}