２分探索法：binary search †
2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。
2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。
この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。
この方法がすごいのは、要素数が倍になっても繰り返しは一回しか増えないことです。別の言い方をすると、O(log n)のアルゴリズムということです。これがどれほどすごいかというと、たとえ100万要素あっても、たかだか20回程度の繰り返しで済む。
- In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element. The method reduces the number of elements needed to be checked by a factor of two each time, and finds the target value, if it exists in logarithmic time.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
