🃏 Card Query Algorithm 詳細解析

📝 問題の概要

目標： 以下の2種類のクエリを効率的に処理する

🔍 二分探索（Lower Bound）の動作原理

アルゴリズムの概要

ソートされた配列で、target以上の値が最初に現れる位置を効率的に見つけます。

例：配列 [10, 20, 30, 40, 50] で target = 25 を検索

初期状態:
10
20
30
40
50
left=0, right=5, target=25
Step 1: mid = (0+5)/2 = 2, arr[2] = 30
10
20
30
40
50
30 ≥ 25 なので right = 2
Step 2: mid = (0+2)/2 = 1, arr[1] = 20
10
20
30
40
50
20 < 25 なので left=2
結果: left = right = 2 → 位置2に挿入
10
20
25
30
40
50
挿入後もソート順を保持

➕ カード挿入（Insert Sorted）の動作

処理の流れ

例：配列 [10, 30, 40] に値 25 を挿入

挿入前
10
30
40
挿入後
10
25
30
40
手順:
  1. 二分探索で挿入位置を特定 (位置1)
  2. Array.splice(1, 0, 25) で挿入実行
  3. 内部的に位置1以降の要素を右にシフト

🎯 最小差検索（Find Min Difference）の動作

アルゴリズムの戦略

ソートされた配列の特性を活用し、target値に最も近い値を効率的に見つけます。

例：配列 [10, 25, 30, 40] で target = 27 の最小差を検索

Step 1: 二分探索で 27 以上の最初の位置を特定
10
25
30
40
pos = 2 (値30の位置)
Step 2: 候補となる値との差を計算
10
25
30
40
|30 - 27| = 3, |25 - 27| = 2
最小値 = 2
重要なポイント:
  • ソートされた配列では、targetに最も近い値は必ずlowerBound位置かその直前にある
  • 他の全ての値をチェックする必要がない（O(1)で決定可能）
  • 最大2回の比較で最小差を特定

📊 計算量解析

操作 時間計算量 空間計算量 説明
二分探索 (Lower Bound) O(log n) O(1) 配列を半分ずつ絞り込み
カード挿入 O(n) O(1) 要素の右シフトが主なコスト
最小差検索 O(log n) O(1) 二分探索 + 定数回の比較
全体（Q回のクエリ） O(Q × n) O(n) 最悪ケースでの総計算量

🎮 インタラクティブデモ

アルゴリズムを実際に動作させてみましょう！

現在の配列:
カードがありません
検索中の要素
挿入される値
比較対象

🚀 パフォーマンス最適化のポイント

1. データ構造の選択

  • 配列: メモリ効率が良く、二分探索に適している
  • ソート維持: 挿入時にソート順を保持することで検索を高速化

2. アルゴリズムの工夫

  • 二分探索: O(log n)の検索により大量データでも高速
  • 最小差計算: 全要素をチェックせず、候補を2個に絞る

3. メモリ効率

  • 単一配列: 余計なデータ構造を使わない
  • インプレース操作: 追加のメモリ使用を最小限に抑制