# 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()` のエイリアス。