【C#アルゴリズム】LowerBound vs UpperBound

はじめに

二分探索について勉強している際にLowerBoundとUpperBoundがややこしくてわからなくなったのでまとめました。

二分探索に関する記事はこちらです。
https://zenn.dev/student_blog/articles/dfdec153c88743

一言で

「最小のインデックスを返すか、最大のインデックスを返すか」という観点で考えることができます。

決定的な違い

1. LowerBound:

   • 最小インデックス
     → 配列の中で目標値 k 以上になる最初（最小）のインデックスを返す。

2. UpperBound:

   • 最大インデックス
     → 配列の中で目標値 k を超える最初（最小）のインデックスを返す。

具体例で説明

配列: A = {1, 3, 3, 5, 7}
目標値: k = 3

操作	条件	結果のインデックス
LowerBound	$A[i] \geq k$	1 (最小位置)
UpperBound	$A[i] > k$	3 (最大位置 + 1)

• LowerBound は、「目標値以上になる最小の位置」。
• UpperBound は、「目標値を超える最小の位置（結果的にその範囲の最大位置 + 1）」。

両者の違いを明確化するポイント

LowerBound: $\geq k$

• 探索対象の範囲が「目標値以上」に始まるため、最初の値（範囲の左端）を特定する。

UpperBound: $> k$

• 探索対象の範囲が「目標値より大きい」に始まるため、範囲の境界（範囲の右端 + 1）を特定する。

イメージ

配列のインデックス:	0	1	2	3	4
配列の値 A[i]:	1	3	3	5	7

LowerBound $\geq k$

• 探索条件: 「目標値 3 以上」
• 最初に該当する位置（インデックス）: 1

UpperBound $> k$

• 探索条件: 「目標値 3 を超える」
• 最初に該当する位置（インデックス）: 3

おすすめ

paizaのこの問題　を解くと理解が深まると思います。