🔍 Binary Search Range Finding Algorithm

Left Pointer
Right Pointer
Mid Pointer
Target Value
Found Position

📊 Example: nums = [5,7,7,8,8,10], target = 8

⏱️ Time Complexity

O(log n)

二分探索を2回実行

💾 Space Complexity

O(1)

定数の追加メモリのみ

Initial Array

5
0
7
1
7
2
8
3
8
4
10
5

Target: 8 | Expected Result: [3, 4]

🧠 Algorithm Analysis

1. Find First Position (左端の探索)

戦略: targetを見つけても、より左側に同じ値がある可能性があるため、右側の境界を狭める

Key Point: nums[mid] == target の時、result = mid として記録し、right = mid - 1 で左側を継続探索
2. Find Last Position (右端の探索)

戦略: targetを見つけても、より右側に同じ値がある可能性があるため、左側の境界を狭める

Key Point: nums[mid] == target の時、result = mid として記録し、left = mid + 1 で右側を継続探索
3. Edge Cases Handling
  • 空配列: 即座に [-1, -1] を返却
  • Target不存在: 最初の探索で -1 が返された場合、[-1, -1] を返却
  • 単一要素: 最初と最後の位置が同じ場合を適切に処理