0Pricing
Coding Interview Prep · レッスン

bisect_left と bisect_right

ソート済みリストへの挿入位置を見つけます

「bisect_left と bisect_right」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

定型コードなしで探索する

Python の bisect モジュールを使えば、ソート済みリストに対する検証済みの二分探索を利用できます。ループを手書きしなければ、オフバイワンのバグをデバッグする必要もありません。

import bisect

真偽値ではなく挿入位置

bisect は true や false の代わりに、リストのソート順を保つために値を挿入できるインデックスを返します。このインデックスこそが本当の力です。

a = [1, 3, 3, 3, 7]

bisect_left は左端を返す

bisect_left は、値を配置できる最初の位置を返します。重複がある場合は、等しい要素すべての前になり、後ろになることはありません。

bisect.bisect_left(a, 3)  # 1

bisect_right は右端を返す

bisect_right は、等しい要素の最後の位置の直後を返します。重複がある場合は、一致する値すべての後ろになります。

bisect.bisect_right(a, 3)  # 4

等しい要素を数える

二つの位置の差を取れば、ある値の重複数を O(log n) で数えられます。right から left を引くと、その値が現れる回数になります。

lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo)  # 3

値は存在したか

メンバーシップを確認するには、bisect_left から i を取得し、a[i] が target と等しいことを確認します。まず i がリストの長さに達していないか確認してください。

i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == x

X 以上の最初の要素

bisect_left は、x 以上である最初の要素も見つけます。そのインデックスが、そのまま下限の答えを指します。

i = bisect.bisect_left(a, x)  # first >= x

X より大きい最初の要素

x より厳密に大きい最初の要素が必要ですか。bisect_right を使えば、そのインデックスを直接取得できます。これは上限に相当します。

i = bisect.bisect_right(a, x)  # first > x

挿入してソート順を保つ

insort は適切な位置を見つけて一度の呼び出しで挿入し、リストの順序を保ちます。実行中にソート済みの構造を構築するときに便利です。

bisect.insort(a, 5)  # a stays sorted

範囲内を探索する

省略可能な lo と hi 引数で、探索をスライスの範囲に制限できます。部分範囲だけが必要な場合に、コピーを作らずに済みます。

bisect.bisect_left(a, x, 2, 5)

補助リストでキーを扱う

bisect は要素全体を比較するため、フィールドで探索したい場合は、そのキーだけを並べた補助リストを作り、そちらに対して bisect を使います。

keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)

確認

重複と挿入位置について考えてみてください。

まとめ：bisect を使いこなす

これで挿入位置を見つけ、重複を数え、下限と上限を対数時間で求められるようになりました。ループを書く前に bisect を使えないか考えてください。✨

よくある質問

「bisect_left と bisect_right」レッスンは無料ですか？

はい。「bisect_left と bisect_right」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「bisect_left と bisect_right」で何を学びますか？

ソート済みリストへの挿入位置を見つけます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「bisect_left と bisect_right」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. バグのない基本的な二分探索
  2. bisect_left と bisect_right
  3. First True: 述語二分探索
  4. 答えに対する二分探索
← Coding Interview Prepに戻る