Pythonでターゲット文字より大きい最小の文字を二分探索で見つける方法

ソート済みの小文字アルファベットのリスト letters と、ターゲットとなる文字 t が与えられたとき、リストの中から「t よりも大きい文字のうち最小のもの」を探す問題を考えてみましょう。

このとき、文字は循環(ラップアラウンド)するとします。つまり、target = 'z' で letters = ['a', 'b'] のような場合、'z' より大きい文字が存在しないため、先頭に戻って答えは 'a' になります。

例えば、入力が ["c", "f", "j"] で target が 'a' の場合、'a' より大きい最小の文字は 'c' なので、出力は 'c' となります。

解き方のアプローチ:二分探索

リストがソート済みであるため、二分探索(バイナリサーチ)を使えば O(log n) の計算量で効率的に解くことができます。手順は以下の通りです。

• 左端のインデックス l を 0 に初期化する
• 右端のインデックス r を「リストのサイズ − 1」に初期化する
• l ≤ r の間、以下を繰り返す
  • mid := (l + r) // 2(中央のインデックス)
  • letters[mid] > target ならば、r := mid − 1(答えの候補は左側にある)
  • そうでなければ、l := mid + 1(答えの候補は右側にある)
• ループ終了後、letters[l % リストのサイズ] を返す

最後の「剰余演算(mod)」がポイントです。ターゲットより大きい文字が見つからなかった場合、l がリストの範囲外になるため、mod を取ることで先頭の文字に wrap around させることができます。

実装例

class Solution:
    def nextGreatestLetter(self, letters, target):
        l = 0
        r = len(letters) - 1
        while l <= r:
            mid = (l + r)//2
            if letters[mid] > target:
                r = mid -1
            else:
                l = mid + 1
        return letters[l % len(letters)]
ob = Solution()
print(ob.nextGreatestLetter(["c", "f", "j"], "a"))

入力

["c", "f", "j"], "a"

出力

c

まとめ

このように、ソート済みの文字リストからターゲットより大きい最小の文字を求める問題は、二分探索と剰余演算を組み合わせることでシンプルかつ高速に解決できます。線形探索では O(n) かかるところを、O(log n) まで削減できるのが大きなメリットです。