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 となります。

この問題は通常の二分探索とは異なり、重複した要素が含まれる 点が特徴です。重複があると、どちら側がソート済みなのか判別できないケースが発生するため、その場合には探索範囲を少しずつ狭めていく工夫が必要になります。

アルゴリズムの手順

• low を 0、high を配列のサイズで初期化します
• low < high の間、以下を繰り返します
  • mid := low + (high - low) / 2 を計算します
  • nums[mid] がターゲットと一致すれば 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):
      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

ob1 = Solution()
print(ob1.search([2,5,6,0,0,1,2], 0))

入力

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

出力

True

計算量について

要素がすべてユニークな場合は通常の二分探索と同様に O(log n) で動作しますが、重複要素が多いケースでは探索範囲を狭める処理が必要になるため、最悪計算量は O(n) になる点に注意してください。