\section{\module{bisect} ---
         配列二分法アルゴリズム}

\declaremodule{standard}{bisect}
\modulesynopsis{バイナリサーチ用の配列二分法アルゴリズム。}
\sectionauthor{Fred L. Drake, Jr.}{fdrake@acm.org}
% LaTeX produced by Fred L. Drake, Jr. <fdrake@acm.org>, with an
% example based on the PyModules FAQ entry by Aaron Watters
% <arw@pythonpros.com>.

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

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

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

\begin{funcdesc}{bisect_left}{list, item\optional{, lo\optional{, hi}}}

  ソートされた順序を保ったまま \var{item} を \var{list} に挿入するのに適した
  挿入点を探し当てます。
  リストの中から検索する部分集合を指定するには、パラメーターの \var{lo} と
  \var{hi} を使います。
  デフォルトでは、リスト全体が使われます。
  \var{item} がすでに \var{list} に含まれている場合、挿入点はどのエントリー
  よりも前(左)になります。
  戻り値は、\code{\var{list}.insert()} の第一引数として使うのに適しています。
  \var{list} はすでにソートされているものとします。
  \versionadded{2.1}
\end{funcdesc}

\begin{funcdesc}{bisect_right}{list, item\optional{, lo\optional{, hi}}}
  \function{bisect_left()} と似ていますが、\var{list} に含まれる \var{item}
  のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
  \versionadded{2.1}。
\end{funcdesc}

\begin{funcdesc}{bisect}{\unspecified}
  \function{bisect_right()} のエイリアス。
\end{funcdesc}

\begin{funcdesc}{insort_left}{list, item\optional{, lo\optional{, hi}}}
  \var{item} を \var{list} にソートされた順序で(ソートされたまま)挿入します。
  これは、 \code{\var{list}.insert(bisect.bisect_left(\var{list}, \var{item}, \var{lo}, \var{hi}), \var{item})}
  と同等です。
  \var{list} はすでにソートされているものとします。
  \versionadded{2.1}
\end{funcdesc}

\begin{funcdesc}{insort_right}{list, item\optional{, lo\optional{, hi}}}
  \function{insort_left()} と似ていますが、\var{list} に含まれる \var{item}
  のうち、どのエントリーよりも後ろに \var{item} を挿入します。
\versionadded{2.1}
\end{funcdesc}

\begin{funcdesc}{insort}{\unspecified}
  \function{insort_right()} のエイリアス。
\end{funcdesc}


\subsection{使用例}
\nodename{bisect-example}

一般には、\function{bisect()} 関数は数値データを分類するのに役に立ちます。
この例では、\function{bisect()} を使って、(たとえば)順序のついた数値の区切り点
の集合に基づいて、試験全体の成績の文字を調べます。
区切り点は 85 以上は `A'、 75..84 は `B'、などです。


\begin{verbatim}
>>> grades = "FEDCBA"
>>> breakpoints = [30, 44, 66, 75, 85]
>>> from bisect import bisect
>>> def grade(total):
...           return grades[bisect(breakpoints, total)]
...
>>> grade(66)
'C'
>>> map(grade, [33, 99, 77, 44, 12, 88])
['E', 'A', 'B', 'D', 'F', 'A']
\end{verbatim}

