Pythonで回転ソート済み配列からターゲットを検索する方法を解説

昇順にソートされた配列が、事前に知らされていないあるピボット（軸）を基準に回転されている状況を考えてみましょう。例えば、[0,1,2,4,5,6,7] という配列は、回転によって [4,5,6,7,0,1,2] のようになります。ここでの課題は、指定されたターゲット値をこの配列の中から探し出すことです。ターゲットが配列内に存在すればそのインデックスを返し、存在しなければ -1 を返します。なお、配列には重複した要素は含まれていないものとします。

例えば、配列が [4,5,6,7,8,0,1,2] でターゲットが 0 の場合、0 はインデックス 5 の位置に存在するため、出力は 5 となります。

解法のアプローチ

この問題は、通常の二分探索を応用することで O(log n) の時間計算量で効率的に解けます。ポイントは、回転ソート済み配列をどの位置で分割しても、必ず少なくとも片側の半分は正しくソートされているという性質です。この性質を利用して、ターゲットが存在しうる範囲を半分ずつ絞り込んでいきます。

具体的な手順は以下の通りです。

• low := 0、high := 配列の長さ と初期化する
• low < high の間、以下を繰り返す
  • mid := low + (high - low) / 2 として中央の位置を求める
  • arr[mid] == target であれば mid を返す
  • arr[low] <= arr[mid] の場合（左半分がソート済みの場合）
    • target >= arr[low] かつ target < arr[mid] であれば high := mid、そうでなければ low := mid + 1
  • それ以外の場合（右半分がソート済みの場合）
    • target <= arr[high - 1] かつ target > arr[mid] であれば low := mid + 1、そうでなければ high := mid
• ループを抜けても見つからなければ -1 を返す

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution(object):
   def search(self, nums, target):
      low = 0
      high = len(nums)
      while low<high:
         mid = low + (high-low)//2
         if nums[mid] == target:
            return mid
         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 -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

入力

[4,5,6,7,8,0,1,2]
0

出力

5

このコードでは、まず中央の要素とターゲットを比較し、一致していれば即座にインデックスを返します。一致しない場合は、左半分と右半分のどちらが正しくソートされているかを判定し、ターゲットがソート済み側の範囲に収まるかどうかで探索範囲を更新します。これにより、配列が回転していても線形探索ではなく対数時間での検索が可能になります。