lower_bound (最初に >= target の位置)
lower_bound (最初に >= target の位置)
このレッスンで分かること
- 「等しい値があったら即 return」ではなく、「境界まで詰めきってから return」が
lower_boundの本質ですlower_boundはソート済み配列で「target以上の値が最初に現れるindex」を返す関数です- 配列の長さを
nとして、戻り値は次のいずれかになります
lower_bound とは
ソート済み配列で target 以上の値が最初に現れる index を返す lower_bound を二分探索で実装します。
lower_bound は ソート 済み配列で「target 以上の値が最初に現れる index」を返す関数です。二分探索 の応用で、計算量 は O(log n)。C++ の std::lower_bound、Python の bisect.bisect_left と同じ概念です。Java には直接の相当物はなく、Collections.binarySearch は要素が見つからない場合に -(挿入位置)-1 を返す仕様であり、重複時に左端を保証しないため変換が必要です。
普通の二分探索は「等しい値を探す」、
lower_boundは「境界を探す」。応用範囲が広く、競プロでも実務でも頻出のテクニックです。
戻り値の仕様
配列の長さを n として、戻り値は次のいずれかになります。
- 配列内に
target以上の要素がある場合、その最初の位置 - 配列内に
target以上の要素がない場合、n(末尾を 1 つ超えた位置)
lower_bound の便利なところは、target が配列に存在しなくても 挿入位置 が分かることです。ソート を維持したまま target を挿入するなら、戻り値の位置に入れれば OK です。
例
配列 [1, 3, 5, 5, 7, 9] に対して:
| target | lower_bound の戻り値 | 意味 |
|---|---|---|
0 | 0 | 全要素が target より大きい |
5 | 2 | 5 が最初に出現する位置 |
6 | 4 | 5 より大きい最小の値 (7) の位置 |
9 | 5 | 9 の最初の位置 |
10 | 6 | 該当なし、配列末尾を超えた位置 |
実装
lower_bound は 二分探索 のテンプレを少しいじるだけで作れます。条件は arr[mid] < target か arr[mid] >= target か、です。
Python
def lowerBound(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] < target:
low = mid + 1
else:
high = mid
return lowJavaScript
function lowerBound(arr, target) {
let low = 0;
let high = arr.length;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}区間の閉じ方の違い
通常の二分探索 (等しい値を探す版) と lower_bound では 高い側 (high) の初期値と更新方法が異なります。
highの初期値はn(n-1ではない)- ループ条件は
low < high(<=ではない) midを見つけてもreturnしない (境界を求めるため最後まで詰める)
「等しい値があったら即 return」ではなく、「境界まで詰めきってから return」が
lower_boundの本質です。
境界条件のチェック
targetがすべての要素より小さい →0を返すtargetがすべての要素より大きい →nを返すtargetが配列内に複数ある → 最初に現れる位置 を返す
upper_bound (target より大きい最初の位置) も似た形で書けます。upper_bound - lower_bound で target の 出現回数 が求まる、というのは競プロの常套句です。
比較
| 機能 | 戻り値 |
|---|---|
index (普通の二分探索) | 一致する位置、なければ -1 |
lower_bound | >= target の最初の位置、なければ n |
upper_bound | > target の最初の位置、なければ n |
よくある間違い
high = mid - 1にしてしまい、境界が1ずれるlow <= highにしてしまい、無限ループに陥るtargetが見つかったら即returnしてしまい、最初の位置ではなく途中の位置を返してしまうJavaでint mid = (low + high) / 2;と書いてオーバーフローが起きる (low + (high - low) / 2を使う)
やってみよう
[1, 3, 5, 5, 7] に対して 5 で呼ぶと 2 が返ります。6 なら 4、100 なら 5、0 なら 0 です。重複 がある場合は 最初の位置 を返すことを忘れずに。
lower_boundを覚えると、ソート済みデータへの問い合わせのほとんどがO(log n)で書けるようになります。
よくある質問
Q. PUT と PATCH はどう使い分けますか？
A. PUT はリソース全体を置き換え、PATCH は部分更新です。例えばユーザー情報全体を送るなら PUT、メールアドレスだけ変えるなら PATCH が REST の慣習に沿います。冪等性は PUT が保証、PATCH は実装次第になります。
Q. 冪等性とは何ですか？
A. 同じリクエストを何度送っても結果が変わらない性質です。GET / PUT / DELETE は冪等、POST は通常冪等ではありません。ネットワークエラーで再送される可能性がある API では、冪等な操作にしておくと安全です。idempotency-key ヘッダで明示する手法もあります。
Q. DELETE のリクエストにボディを入れて良い？
A. HTTP 仕様上は許されていますが、扱わないライブラリやプロキシも多いため避けるのが無難です。複雑な削除条件はクエリパラメータか、POST /resource/delete のようなアクションエンドポイントを使うとトラブルを避けられます。
次のレッスン
次は ピーク要素検索 で、隣接要素より大きい要素（ピーク）を二分探索で O(log n) で見つける手法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- lower_bound の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. lower_bound とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 二分探索 (O(log n)) で実装する
- 見つからない場合は配列長 n を返す
- 重複がある場合は最初の位置を返す
入出力例
test-cases.txt
lowerBound([1,3,5,5,7,9], 5) → 2
lowerBound([1,3,5,5,7,9], 6) → 4
lowerBound([2,4,6,8], 1) → 0
lowerBound([2,4,6,8], 10) → 4
lowerBound([1,2,3,4,5], 5) → 4
lowerBound([3], 3) → 0