LeetCode 2020-11-20: Search in Rotated Sorted Array II

Search in Rotated Sorted Array II (medium) の挑戦メモ。

問題の概要

• ソート済みの配列が一定量ローテートされた状態にある
• 指定された値がその配列に含まれているかいないかを調べる

考え方

• ソート済みではあるが、ローテートされているせいで二分探索が使えない 😭
  • …と思いがちだが、実は状況を整理すれば二分探索が適用できることがわかるはず 😂
• 状況1: 探している値が配列の右側 (ローテートされた結果の小さい方) にあり、二分する中央の値よりも小さいケース
  • 以下の図でいうところの 1 を探しているとする
  • 
  • target < array[0] < mid という関係にある
  • この場合は left = mid + 1 として二分探索を継続する
• 状況2: 探している値が配列の左側にあり、中央の値よりも小さいケース
  • 状況1 に似ているがちょっと異なる
  • 以下の図の 4 を探しているとする
  • 
  • array[0] < target < mid という関係にある
  • この場合は、right = mid - 1 として二分探索を継続する
• 状況3: 探している値が配列の左側にあり、中央の値よりも大きいケース
  • 以下の図の 9 を探しているとする
  • 
  • mid < array[0] < target という関係にある
  • この場合は、right = mid - 1 として二分探索を継続する
• 状況4: 探している値が配列の右側にあり、中央の値よりも大きいケース
  • 以下の図の 5 を探しているとする
  • 
  • mid < target < array[0] という関係にある
  • この場合は left = mid + 1 として二分探索を継続する
• これらをちゃんと考慮して実装すれば、O(n * log(n)) の時間計算量で解けそう… なものだけど、値の重複があるので実際の最悪計算量は O(n) となってしまうと思われる
• ひとまず実装は 0ms を達成 🎉

コード

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) {
            return false;
        }

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

        // nums[left] != nums[right] となるように調整する
        int left = 0, right = nums.length - 1;
        if (nums[left] == nums[right]) {
            do {
                if (++left >= right) {
                    return false;
                }
            } while (nums[left] == nums[right]);
        }

        if (nums[left] < nums[right]) {
            return Arrays.binarySearch(nums, left, right + 1, target) >= 0;
        }

        int begin = left;
        boolean findLeftArea = nums[left] <= target;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return true;
            }

            if (target < nums[mid]) {
                if (nums[begin] <= nums[mid]) {
                    if (findLeftArea) {
                        // nums[left] <= target < nums[mid]
                        return Arrays.binarySearch(nums, left, mid, target) >= 0;
                    } else {
                        // target < nums[left] <= nums[mid] である
                        left = mid + 1;
                    }

                } else {
                    // nums[mid] は右側エリアにある
                    // target < nums[mid] < nums[left]
                    right = mid - 1;
                }

            } else {  // nums[mid] < target
                if (nums[mid] <= nums[nums.length - 1]) {
                    if (!findLeftArea) {
                        // nums[mid] < target <= nums[right]
                        return Arrays.binarySearch(nums, mid + 1, right + 1, target) >= 0;
                    } else {
                        // nums[mid] <= nums[right] < target
                        right = mid - 1;
                    }

                } else {
                    // nums[right] < nums[mid] < target
                    left = mid + 1;
                }
            }
        }

        return false;
    }
}