🔍 回転されたソート済み配列の探索解析

📊 アルゴリズム概要

問題：回転されたソート済み配列から指定された値を O(log n) で探索
手法：修正された二分探索（Binary Search）
キーポイント：配列を半分に分けると、必ずどちらか一方は完全にソートされている

🎯 Example 1: nums = [4,5,6,7,0,1,2], target = 0

📈 計算量解析

⏱️ 時間計算量

O(log n)

二分探索により、毎回探索範囲を半分に削減するため

💾 空間計算量

O(1)

追加の配列やデータ構造を使用せず、定数個の変数のみ

🔍 アルゴリズムの詳細分析

Step 1: 初期化

let left = 0, right = nums.length - 1; // left = 0, right = 6

探索範囲の両端を設定します。

Step 2: 中央値の計算

const mid = Math.floor((left + right) / 2); // mid = Math.floor((0 + 6) / 2) = 3

現在の探索範囲の中央インデックスを計算します。

Step 3: ソート済み部分の判定

if (nums[left] <= nums[mid]) { // 左半分がソートされている // nums[0]=4, nums[3]=7 → 4 <=7 (true) } else { // 右半分がソートされている }

重要：回転された配列では、必ずどちらか一方の半分が完全にソートされています。

Step 4: ターゲットの範囲判定

// 左半分がソートされている場合 if (nums[left] <= target && target < nums[mid]) { // ターゲットが左半分の範囲内 right=mid - 1; } else { // ターゲットが右半分にある left=mid + 1; }

ソートされている部分でターゲットが範囲内にあるかチェックし、探索範囲を絞り込みます。

🎪 他のケースの解析

Case 2: nums = [4,5,6,7,0,1,2], target = 3 (存在しない場合)

同様の手順で探索を進めますが、最終的に left > right になり、-1 を返します。

Case 3: nums = [1], target = 0 (単一要素の配列)

配列に1つの要素しかない場合、1回の比較で結果が決まります。

🚀 最適化のポイント