81. Search in Rotated Sorted Array II - Medium

前往題目

想法

• Binary Search
• 先找pivot

思路

1. Binary Search
2. 搜尋的時候判斷mid是在哪個部分，左還是右，然後再判斷target是否在範圍裡，這樣才能確切知道到底要往左還是右搜尋

原本以為要先找出pivot，這題的關鍵是找到方法確切判斷要往左還是往右找，因為有可能左、中、右的數字都一模一樣，而解決辦法就是只能一格一格移動

Code

class Solution {
    public boolean search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            // Check if found target
            if (nums[mid] == target)
                return true;
            else if (nums[l] < nums[mid]) { // Mid is in the left portion
                // Further check if the target is in between
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else if (nums[l] > nums[mid]) { // Mid is in the right portion
                // Further check if the target is in between
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                l += 1;
            }
        }

        return false;
    }
}