· 開発

二分探索の挿入位置：bisect・lower_bound・binarySearch は何を返すのか

値がないときや重複があるときに Python の bisect、C++ の lower_bound、Java の Arrays.binarySearch が返す位置と、それぞれの前提条件を公式ドキュメントと C++ 規格で比べました。

開発アルゴリズム

二分探索は値を探す方法として習いますが、コードを書くと別の問いにもよく出会います。この値を入れるなら何番目か、という問いです。Python、C++、Java はどれも二分探索の API を備えていますが、戻り値の意味は同じではありません。

次の配列で比べてみます。

a = [1, 2, 4, 5, 5, 6]

挿入位置は要素ではなく境界

挿入位置が指すのは要素ではなく、要素と要素のすき間です。6個の要素には、0から6まで7つのすき間があります。

値5には2つの境界があります。

  • 5未満 | 5以上 → 3
  • 5以下 | 5より大きい → 5

最初の境界は最初の5の前、次の境界は最後の5の後ろです。値が存在しない場合、2つの境界は同じ位置になります。3なら、どちらもインデックス2です。

Python：bisect_left と bisect_right

Python の公式ドキュメントは、この2つの境界をそのまま定義しています。

import bisect

a = [1, 2, 4, 5, 5, 6]
bisect.bisect_left(a, 5)   # 3
bisect.bisect_right(a, 5)  # 5
bisect.bisect_left(a, 3)   # 2

この結果は Python 3.14.7 で実行して確認しました。

これらの関数は __lt__ だけを呼び、__eq__ は呼びません。そのため、戻り値だけでは値が存在するかどうかは分かりません。bisect_left の結果が配列の範囲内か、その位置の要素が探す値と等しいかを別に確認する必要があります。

key 引数は Python 3.10 で追加されました。bisect_left と bisect_right では、key は配列の要素にだけ適用され、x には適用されません。

入力はソート済みであることが前提です。また、公式ドキュメントは bisect の関数がスレッドセーフではないと明記しています。同じシーケンスを複数のスレッドから同時に検索したり、探索中に別のスレッドが変更したりすると、結果は未定義です。

C++：lower_bound と upper_bound

C++ の lower_bound は bisect_left と同じ境界を返します。upper_bound は bisect_right に対応します。

std::vector<int> a{1, 2, 4, 5, 5, 6};

std::lower_bound(a.begin(), a.end(), 5) - a.begin();  // 3
std::upper_bound(a.begin(), a.end(), 5) - a.begin();  // 5

この結果は Apple clang 17 と -std=c++17 で実行して確認しました。

C++ 規格が求める条件は、範囲全体がソート済みであることではなく、比較式について**区分化（partitioned）**されていることです。e < value を満たす要素が、満たさない要素より前に並んでいれば条件を満たします。ソートされていない範囲でも、特定の検索値についてはこの条件を満たす場合があります。cppreference は、この条件を破った場合を未定義動作と説明しています。

Java：Arrays.binarySearch

Java はキーが見つかれば、そのインデックスを返します。見つからなければ次の値を返します。

-(挿入位置) - 1

挿入位置は、キーより大きい最初の要素のインデックスです。そのような要素がなければ配列の長さになります。例の配列で3の挿入位置は2なので、仕様上の戻り値は -3 です。負の戻り値を r とすると、-(r + 1) で挿入位置に戻せます。

注意が必要なのは重複値です。Javadoc は、同じ値が複数ある場合にどのインデックスが返るかを保証していません。5を探すと3が返ることも4が返ることもあります。**Arrays.binarySearch は lower_bound ではありません。**最初の位置が必要なら、そのための境界探索を使う必要があります。

Java の配列は検索前にソートされていなければなりません。そうでない場合、結果は未定義です。

戻り値の比較

API 値があるとき 値がないとき 重複値 入力条件
Python bisect_left 最初の位置 挿入位置 いちばん左の前 ソート済み
Python bisect_right 最後の次 挿入位置 いちばん右の後ろ ソート済み
C++ lower_bound 最初の位置 挿入位置 いちばん左の前 比較式について区分化
C++ upper_bound 最後の次 挿入位置 いちばん右の後ろ 比較式について区分化
Java binarySearch 一致するインデックス -(挿入位置) - 1 どれが返るかは未規定 ソート済み

どの API も、必要な順序条件を呼び出し前に検証してくれるわけではありません。Python と Java はソート済みの入力を、C++ は探索に使う比較式について区分化された範囲を前提とします。

ソートが同じ値の順序をどう扱うかは、安定ソートの記事で確認できます。

ブログへ