Pythonでソート済みリストに要素を挿入すべきインデックスを二分探索で見つける方法

昇順にソートされた数値のリスト nums と、別の数値 target が与えられたとします。このとき、nums のソート状態を保ったまま target を挿入できるインデックスを求めます。もし target がすでにリスト内に存在する場合は、挿入可能な最大のインデックスを返します。さらに、ライブラリ関数を使用せず、O(log n) の計算量で解くことが条件です。

たとえば、入力が nums = [1,5,6,6,8,9]、target = 6 の場合、出力は 4 になります。これは、6 がすでにリスト内に存在するため、挿入できる最大のインデックスが 4 であり、挿入後の配列は [1,5,6,6,6,8,9] となるからです。

問題のポイント

• リストは必ず昇順にソートされている前提である
• 重複した値が存在する場合は、その中で最も右側（最大）の挿入位置を返す
• 線形探索では O(n) かかるため、O(log n) を達成するには二分探索が必要

解法のアプローチ：二分探索

この問題は「二分探索（バイナリサーチ）」を応用することで効率的に解けます。探索範囲を半分ずつ絞り込みながら、挿入候補となる位置を更新していくのがポイントです。

アルゴリズムの手順

• left := 0
• right := リストのサイズ − 1
• ans := 0
• left ≤ right の間、以下を繰り返します：
  • mid := (left + right) / 2 の小数点以下を切り捨てた値
  • target ≥ nums[mid] の場合：
    • ans := mid + 1（挿入候補位置を記録）
    • left := mid + 1（右半分を探索）
  • それ以外の場合：
    • right := mid − 1（左半分を探索）
• 最後に ans を返します

Pythonでの実装例

理解を深めるために、以下の実装をご覧ください。

def solve(nums, target):
    left, right = 0, len(nums) - 1
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if target >= nums[mid]:
            ans = mid + 1
            left = mid + 1
        else:
            right = mid - 1
    return ans

nums = [1,5,6,6,8,9]
target = 6
print(solve(nums, target))

動作のポイント

target >= nums[mid] のときに ans = mid + 1 を記録し、探索範囲を右側へ広げ続けることで、同じ値が複数ある場合でも最も右側の挿入位置が最終的に残ります。これにより「最大のインデックスを返す」という要件を満たせます。

入力

[1,5,6,6,8,9], 6

出力

4