PYTHON の二分法アルゴリズム関数

の 二等分する Python のモジュールは、ソートされたリスト内の要素を検索し、新しい要素を挿入するための正しい位置を見つけ、リストがソートされた状態を維持するように新しい要素を挿入するための、シンプルで高速な (バイナリ検索ベースの) 関数を提供します。

なぜ Bisect モジュールが必要なのでしょうか?

ソートされたリスト内を検索し、挿入ポイントを見つけるための二分検索操作に役立ちます。
順序を維持しながら並べ替えられたリストに要素を挿入する効率的な方法を提供します。
挿入するたびに手動で並べ替える必要がなくなり、時間と労力を節約できます。
bisect() bisect_left() bisect_right() および insort() などの関数を提供して、クリーンに最適化されたコードを実現します。
リーダーボードのランク付けされたデータの管理などのタスクや、並べ替えられたデータの挿入/検索を伴うシナリオに最適です。

Bisect モジュールのコア機能

bisect モジュールは主に 2 種類の機能を提供します。

挿入ポイントの検索 (挿入なし)
要素を正しい位置に挿入する

1. 挿入ポイントの検索

これらの関数は、リストをソートしておくために新しい要素を挿入するインデックスを返します。

a) bisect.bisect(): 要素の右端の挿入ポイントを返します。要素がすでに存在する場合、挿入ポイントは既存のエントリの後にあります。

bisect.bisect(リスト番号 beg=0 end=len(リスト))

パラメータ:

リスト： 並べ替えられたリスト。
番号: 挿入する要素。
懇願します: 検索用の開始インデックス (オプション)。
終わり： 検索用の終了インデックス (オプション)。

b) bisect.bisect_left(): 要素の左端の挿入ポイントを返します。要素が存在する場合、挿入ポイントは既存のエントリの前になります。

Javaの数学

bisect.bisect_left(リスト番号 beg=0 end=len(リスト))

c) bisect.bisect_right(): bisect.bisect() と同じで、右端の挿入ポイントを返します。

bisect.bisect_right(リスト番号 beg=0 end=len(リスト))

例：さまざまな二分関数を使用して、並べ替えられたリスト内の値 4 の挿入インデックスを見つけます。

Python

import bisect li = [1 3 4 4 4 6 7] print(bisect.bisect(li 4)) # right print(bisect.bisect_left(li 4)) # left print(bisect.bisect_right(li 4 0 4)) # subright

出力

5 2 4

説明：

二等分(li 4): リストの最後の 4 の後の右端の位置 (インデックス 4) が検索されるため、5 が返され、挿入ポイントは 5 になります。
bisect_left(li 4): リストの最初の 4 より前の左端の位置 (インデックス 2) が見つかるため、2 を返します。
bisect_right(li 4 0 4): サブリストでのみ機能します それ[0:4] サブリストの最後の 4 の後に 4 を挿入するため、4 を返します。

2. 要素の挿入

これらの関数は、並べ替えを維持するために要素を適切な位置に挿入します。

要素を右端の位置に挿入します。 bisect() 関数とは異なり、これは要素を挿入することによって実際にリストを変更します。

bisect.insort(list num beg=0 end=len(list))

パラメータ:

リスト： 並べ替えられたリスト。
番号:
頼む (オプション): 挿入の開始インデックス (デフォルトは 0)。
終了 (オプション): 挿入用の終了インデックス (デフォルトは len(list))。

b) bisect.insort_left(): 要素を左端の位置に挿入します。

bisect.insort_left(list num beg=0 end=len(list))

c) bisect.insort_right(): 要素を右端の位置に挿入します (insort() と同様)。

文字から文字列へ

bisect.insort_right(list num beg=0 end=len(list))

例：さまざまな挿入戦略を使用してソートされたリストを維持しながら、値 5 をソートされたリストに挿入します。