下限と上限
bisect_leftとbisect_rightをゼロから実装し、対象値の最初と最後の位置を求める方法に応用します。
「下限と上限」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
Lower Bound と Upper Bound とは
ソート済み配列におけるターゲット値のlower boundは、ターゲット以上の値を持つ最初の要素のインデックスです（bisect_leftと呼ばれることが多いです）。upper boundは、ターゲットより大きい値を持つ最初の要素のインデックスです（bisect_right）。この2つを組み合わせると、ターゲットのすべての出現位置を範囲として取得でき、O(log n)の範囲クエリを実現できます。
この2つの操作は、出現回数のカウント、範囲の検索、挿入位置の検索など、多くの面接問題の基礎になります。
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Lower Bound（bisect_left）を実装する
bisect_left(arr, x)は、arr[i] >= xを満たす最も左側のインデックスiを返します。すべての要素が小さい場合はlen(arr)を返します。この実装では排他的な上限を使用します。つまり、hi = len(arr)とし、ループ条件をlo < hiにして、arr[mid] >= xのときはhi = midに更新します。これにより、答えが最も左側の有効な位置に収束します。
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Upper Bound（bisect_right）を実装する
bisect_right(arr, x)は、arr[i] > xを満たす最も左側のインデックスiを返します。bisect_leftとの違いは1行だけです。条件がarr[mid] < xからarr[mid] <= xに変わります。arr[mid] <= xの場合、答えはmidより右側にあるため、lo = mid + 1に設定します。それ以外の場合は右側から範囲を狭めます。
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5両方の Bound で出現回数を数える
ソート済み配列内のターゲットの出現回数をO(log n)で数えるには、両方のboundを使います。count = bisect_right(arr, target) - bisect_left(arr, target)です。countが0なら、ターゲットは存在しません。これは線形走査より大幅に高速で、ソート済みデータに対する頻度クエリの標準的な方法です。
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1ターゲットの最初と最後の位置を求める
LeetCode 34「ソート済み配列内の要素の最初と最後の位置」は、[first_idx, last_idx]をO(log n)で返す問題です。最初の位置はbisect_left(arr, target)で求められます。ただし、arr[result] == targetの場合に限ります。最後の位置はbisect_right(arr, target) - 1です。どちらかの確認に失敗した場合は、[-1, -1]を返します。
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]挿入位置（LeetCode 35）
LeetCode 35「Search Insert Position」は、配列をソート済みのまま保つにはターゲットをどこに挿入すればよいかを問う問題です。これはまさにbisect_left(arr, target)です。ターゲットが存在する場合、bisect_leftはそのインデックスを返します。存在しない場合は、ターゲットを挿入すべきインデックスを返します。特別な場合分けは必要ありません。同じ関数でどちらの状況にも対応できます。
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)bisect_left と bisect_right の違い
重複がない場合、bisect_leftとbisect_rightは同じインデックスを返します。違いが生じるのは、ターゲットが複数回出現する場合だけです。bisect_leftは最初の要素を指し、bisect_rightは最後の要素の1つ後ろを指します。既存の要素の前に挿入したいのか（left）、後ろに挿入したいのか（right）に応じて、適切な方を選んでください。
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4ソート済みデータの頻度クエリに Bound を適用する
ソート済み配列に対して範囲ごとの頻度クエリを効率的に何度も実行する必要がある場合は、まずソート済み配列を一度作成し、各クエリでbisectを使います。各クエリで「[lo, hi]に含まれる要素はいくつか」を、O(n)ではなくO(log n)で求められます。このパターンは、ソート後に値の範囲内にある要素を数える問題でよく登場します。
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)カスタムキーによる二分探索
検索キーが格納されている値そのものではなく、そこから導出されるプロパティである場合があります。Pythonのbisectモジュールはkey関数を直接サポートしていませんが、ループ内でkeyを適用して手動で二分探索できます。このパターンは、オブジェクトの属性の1つを基準にリストを検索する場合に使われます。
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Bound でよくある面接のミス
最もよくあるミスは、bisect_leftを呼び出した後の確認を忘れることです。この関数は常に有効な挿入位置のインデックスを返しますが、その位置の要素がターゲットと等しいことは保証しません。ターゲットが見つかったと判断する前に、必ずarr[result] == targetを確認してください。
2つ目のミスは、最初の出現位置が必要なのにbisect_rightを使うことです。bisect_rightは最後の出現位置の1つ後ろを返すため、1を引くと得られるのは最初ではなく最後の位置です。
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # Falseまとめ：bisect_left と bisect_right の使い分け
bisect_leftは、ターゲットの最初の出現位置、既存の要素を右側へ移動させる挿入位置、またはターゲットの存在確認が必要な場合に使います。bisect_rightは、最後の出現位置の1つ後ろ、既存のすべての要素の後ろへの挿入位置、またはターゲット以下の要素数が必要な場合に使います（これはbisect_right(arr, target)と等しくなります）。
どちらもO(log n)で実行され、Pythonの標準ライブラリに含まれているため、面接官から一から実装するよう求められない限り、直接インポートして使えます。
理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、bisect_leftはターゲット以上の最初の要素を見つけること、bisect_rightはターゲットより大きい最初の要素（最後の出現位置の1つ後ろ）を見つけること、そして両者の差によって出現回数をO(log n)で求められることを学びました。次は、配列のインデックスではなく、答えの候補範囲を探索する答え空間の二分探索について学びます。
よくある質問
「下限と上限」レッスンは無料ですか？
はい。「下限と上限」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「下限と上限」で何を学びますか？
bisect_leftとbisect_rightをゼロから実装し、対象値の最初と最後の位置を求める方法に応用します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「下限と上限」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。