5.5 `bisect` -- 配列二分法アルゴリズム

このモジュールは、挿入の度にリストをソートすることなく、リストをソートされた順序に保つことをサポートします。大量の比較操作を伴うような、アイテムがたくさんあるリストでは、より一般的なアプローチに比べて、パフォーマンスが向上します。

動作に基本的な二分法アルゴリズムを使っているので、bisect と呼ばれています。ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界条件はすでに正しいです!)。

次の関数が用意されています。

bisect_left( list, item[, lo[, hi]]): ソートされた順序を保ったまま item を list に挿入するのに適した挿入点を探し当てます。リストの中から検索する部分集合を指定するには、パラメーターの lo と hi を使います。デフォルトでは、リスト全体が使われます。 item がすでに list に含まれている場合、挿入点はどのエントリーよりも前(左)になります。戻り値は、list.insert() の第一引数として使うのに適しています。 list はすでにソートされているものとします。バージョン 2.1 で新たに追加された仕様です。

bisect_right( list, item[, lo[, hi]]): bisect_left() と似ていますが、list に含まれる item のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。バージョン 2.1 で新たに追加された仕様です。。

bisect( ...): bisect_right() のエイリアス。

insort_left( list, item[, lo[, hi]]): item を list にソートされた順序で(ソートされたまま)挿入します。これは、 list.insert(bisect.bisect_left(list, item, lo, hi), item) と同等です。 list はすでにソートされているものとします。バージョン 2.1 で新たに追加された仕様です。

insort_right( list, item[, lo[, hi]]): insort_left() と似ていますが、list に含まれる item のうち、どのエントリーよりも後ろに item を挿入します。バージョン 2.1 で新たに追加された仕様です。

insort( ...): insort_right() のエイリアス。

ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。