回転ソート配列 II の検索を Python で実装する方法【二分探索の応用】

昇順にソートされた配列が、事前に分からないあるピボットを軸として回転されている状況を考えてみましょう。例えば、配列が [0,0,1,2,2,5,6] である場合、回転によって [2,5,6,0,0,1,2] のようになっている可能性があります。

この配列の中から特定のターゲット値を検索します。ターゲットが配列内に存在すれば true を、存在しなければ false を返します。例えば、配列が [2,5,6,0,0,1,2] でターゲットが 0 の場合、出力は true となります。

この問題は「回転ソート配列の検索 II」として知られており、通常の二分探索との違いは、配列に重複した要素が含まれている点です。重複があると nums[low] == nums[mid] の場合に、どちら側がソート済みか判断できなくなるため、特別な処理が必要になります。

アルゴリズムの手順

• low := 0、high := 配列のサイズ とする
• low < high の間、以下を繰り返す
  • mid := low + (high - low) / 2
  • nums[mid] == target なら true を返す
  • nums[low] == nums[mid] かつ nums[high - 1] == nums[mid] の場合
    • low を 1 増やし、high を 1 減らして次の反復へ進む（重複による判定不能領域を狭める）
  • nums[low] <= nums[mid] の場合（左半分がソート済み）
    • target >= nums[low] かつ target < nums[mid] なら high := mid、そうでなければ low := mid + 1
  • それ以外の場合（右半分がソート済み）
    • target <= nums[high - 1] かつ target > nums[mid] なら low := mid + 1、そうでなければ high := mid

ループが終了してもターゲットが見つからなければ、false を返します。

実装例（Python）

以下の実装例を見ると、理解が深まるでしょう。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        low = 0
        high = len(nums)
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return True
            if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
                low += 1
                high -= 1
                continue
            if nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid
                else:
                    low = mid + 1
            else:
                if target <= nums[high-1] and target > nums[mid]:
                    low = mid + 1
                else:
                    high = mid
        return False

入力例

[2,5,6,0,0,1,2]
0

出力例

true

計算量の分析

• 時間計算量： 平均 O(log n)。ただし、すべての要素が同一値であるような最悪ケースでは、境界を狭める処理の影響で O(n) となります。
• 空間計算量： O(1)。追加のメモリは不要です。