Search in Rotated Sorted Array II

アルゴリズム概要

問題

回転されたソート済み配列（重複要素あり）から、指定されたターゲット値を効率的に検索

手法

修正版バイナリサーチ：通常の二分探索を回転配列と重複要素に対応

効率性

平均：O(log n) / 最悪：O(n) - 重複要素により線形時間の可能性

ステップバイステップ解説

1

初期化

left = 0, right = n-1 で検索範囲を設定

2

中央値計算

mid = (left + right) // 2 で中央のインデックスを計算

3

ターゲット確認

nums[mid] == target の場合、True を返す

4

重複処理

nums[left] == nums[mid] == nums[right] の場合、両端を縮める

5

ソート判定

左半分または右半分のどちらがソートされているかを判定

6

範囲更新

ターゲットの位置に応じて検索範囲を更新

Python実装

LeetCode Solution

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left: int = 0
        right: int = len(nums) - 1

        while left <= right:
            mid: int = (left + right) // 2
            if nums[mid] == target:
                return True

            # Handle duplicates
            while left < mid and nums[left] == nums[mid] and nums[right] == nums[mid]:
                left += 1
                right -= 1

            # Left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

# Test Examples
solution = Solution()

# Example 1: [2,5,6,0,0,1,2], target = 0
print(solution.search([2,5,6,0,0,1,2], 0))  # True

# Example 2: [2,5,6,0,0,1,2], target = 3
print(solution.search([2,5,6,0,0,1,2], 3))  # False

インタラクティブ可視化

配列: [4, 5, 6, 7, 0, 1, 2] - ターゲット: 0

Left: 0 Mid: 3 Right: 6

ステップ 0: 初期化完了

配列の初期状態です。検索を開始してください。

計算量解析

時間計算量

O(log n)

平均ケース

最悪ケース

O(n)

全要素が重複

空間計算量

O(1)

定数空間

重複要素による影響

重複要素が多い場合、どちらの半分がソートされているかを判定できないケースが発生します。この場合、両端から重複を除去する必要があり、最悪の場合は線形時間O(n)となります。