33. Search in Rotated Sorted Array @ LeetCode

インタビュー対策に近いコーディングの鍛錬としてLeetCodeを進めています。

数百に近い問題があり、"何から始めたら…? 1から解こう！→ 3日坊主" の未来が見えたので、新井康平さんの記事 "コーディング面接対策のために解きたいLeetCode 60問" (https://1kohei1.com/leetcode/) の問題を徹底的に理解していくことから始めようと思っています。

今日はその中の1問を取り上げます。

問題

LeetCode 33. Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/)

昇順にソートされた配列をあらかじめ知らないピボットで
回転させたとします（ex. [0,1,2,4,5,6,7]→[4,5,6,7,0,1,2]）。
検索対象の値が与えられます。配列の中に見つかった場合はそのインデックスを返し、
そうでない場合は -1 を返します。
配列の中に重複したものが存在しないと仮定しても構いません。
アルゴリズムの実行時の複雑さは，O(log n) のオーダーでなければなりません。

例1.
入力: nums = [4,5,6,7,0,1,2], target = 0
出力: 4

例2.
入力: nums = [4,5,6,7,0,1,2], target = 3
出力: -1

訳: DeepL(https://www.deepl.com/home)、少し修正

方針

後述するYoutube解説でも配信者が述べていますが、シンプルな問題設定でバイナリサーチへの理解を問う 良問です。

今回の問題設定では、ソート済みリストの一部がピボットしていることから、ソート済みリストを前提としているバイナリサーチをそのまま使うことはできません。

そこで、ピボット位置の特定によりソート済みの部分リストを見つけることで、単純なバイナリサーチに落とし込むことができるという流れになります。

AC解答

情けないことに、初見で単純なバイナリサーチをかましてWA連発したため、以下のYoutube解説(Java)を参考に解答しました。(ほぼ写経やないかい)

LeetCode 33. Search in Rotated Sorted Array

丁寧な説明で英語も聞き取りやすかった。

---

class Solution:
    def search(self, nums: List[int], target: int) -> int:
            # リストが空の場合
        if nums is None or len(nums) == 0:
            return -1
          
        # pivotのindex(=start)を見つける
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        start = left
        left, right = 0, len(nums) - 1
        
        # 探索する部分リストの選択
        if nums[start] <= target <= nums[-1]:
            left = start
        else:
            right = start -1
        
        # targetが含まれる(であろう)部分リストへの純粋なバイナリサーチ
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            return -1