二分検索

デジタル大辞泉

にぶん‐けんさく【二分検索】

読み方：にぶんけんさく

《binary search》⇒二分探索

ウィキペディア

二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/24 16:42 UTC 版)

探索 > 二分探索

二分探索

クラス	探索アルゴリズム
データ構造	配列
最悪計算時間	${\displaystyle O\left(\log n\right)}$ 二分探索アルゴリズムの視覚化。探索目標値は7である。 二分探索（英: binary search）もしくはバイナリサーチとは、計算機科学において整列配列（英語版）の中から目標の値の位置を見つけ出す探索アルゴリズム[1][2]。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。 二分探索は対数時間（英語版）で動作するアルゴリズムであり、最悪のケースにおいて比較演算を ${\displaystyle O(\log n)}$ 二分探索の手順。 function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m return unsuccessful ${\displaystyle {\frac {R-L}{2}}}$ 二分探索は近似一致の計算にも応用できる。探索対象値の5が配列中に存在しない場合にも二分探索によって順位 (Rank)、直前要素 (Predecessor)、直後要素 (Successor)、最近接要素 (Nearest neighbor) が取得できる。 上記の手続きは完全一致の判定のみを行って目標値の位置を見つけるものである。しかし、二分探索は整列配列を対象としているため、近似一致の判定を行うように拡張することは容易である。たとえば、与えられた値に対して、順位（より小さい要素の数）、直前要素（次に値が小さい要素）、直後要素（次に値が大きい要素）、最も近い要素を求めるなどである。2つの値について順位を求めることで、それらの間にある要素数を求める範囲クエリ（英語版）も実行可能である[8]。 順位クエリは左端要素を求める手続きによって実行できる[8]。 直前要素クエリは順位クエリによって実行できる。目標値の順位が ${\displaystyle r}$ 二分探索を表す木構造。ここで探索対象となっている配列は ${\displaystyle [20,30,40,50,80,90,100]}$ 二分探索の最悪ケースでは、木構造の探索が最も深いレベルに到達する。最良ケースとなるのは目標値が配列の中央要素と一致したときである。 二分探索の性能のうち比較回数に関する部分は、手続きを二分探索木で表すことで評価できる。二分探索木の根ノードは配列の中央要素である。その子ノードは、左側が配列の前半の中央要素、右側が後半の中央要素となる。それ以降も同様に構築される。探索は根ノードから開始され、現在のノードの値を目標値と比較して大小に応じて左右の部分木をたどっていく[3][11]。 最悪の場合、二分探索は比較ループを ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 二分探索木は二分探索と類似したアルゴリズムで検索される。 二分探索木は二分探索の原理に基づいて機能する二分木のデータ構造である。すべてのレコードが整列しており、各レコードの探索は二分探索に似たアルゴリズムによって平均して対数時間で行うことができる。二分探索木では挿入や削除の処理も平均で対数時間となり、整列配列における線形時間の挿入・削除より高速となりうる。また二分木は範囲検索や近似検索など整列配列で可能なすべての操作が実行可能である[19][24]。 しかしながら、実際の二分探索木は完全に平衡ではない可能性が高く、そのため検索効率では整列配列の二分探索に劣るのが普通である。ノードの自動的な再配置によって自己平衡を行う平衡二分探索木においても、理想的な最小階層数の構造が得られることはまれである。平衡でない二分探索木では、内部ノードの多くが子ノードを1つしか持たず探索時間が平均・最悪ともに ${\textstyle n}$ ユニフォーム二分探索では、上限・下限のインデックスではなく、現在の中点と2つの次の中点候補との間のインデックス差を記憶する。 ユニフォーム二分探索 (uniform binary search) では、配列インデックス範囲の上限と下限を記憶するのでなく、現在の中央要素と次の反復における中央要素のインデックス差を記憶する。具体的には、各回の反復におけるインデックス差を格納したルックアップテーブルをあらかじめ計算しておく。たとえば、0から10までのインデックスを持つ11要素の配列を探索する場合、最初の中央要素のインデックス ${\displaystyle m}$ 指数探索の概念図。長い配列から探索対象値を含む範囲の部分配列を抜き出し、それに対して二分探索を実行する。 指数探索（英語版）は二分探索を無限長のリストに拡張したものである。このアルゴリズムはまず「インデックスが2のべき乗であり、かつ探索対象の値より大きい最初の要素」を見つけることから始め、そのインデックスを上限に設定した上で二分探索に切り替える。探索対象の位置を ${\textstyle x}$ 線形補間による内挿探索の概念図。このケースでは、配列内の目標値の位置が正確に推定されため探索が不要となっている。実装によっては目標値の位置を推定するために別の関数が用いられる。 内挿探索（英語版）では、中間点を計算するのではなく、要素の最小値と最大値、ならびに配列の長さを考慮して目標値の位置を推定する。その前提には、中間点は多くの場合で最良の推定位置ではないという点がある。たとえば、目標値が要素の最大値に近い場合、その値は配列の末尾近くに位置している可能性が高い[40]。 一般的には内挿関数として線形補間が用いられる。配列を ${\displaystyle A}$ フラクショナル・カスケーディングでは、カスケードされた配列のそれぞれに、前段の配列から1つおきで抽出した要素へのポインタが織り込まれる。これにより、最後の配列に対して二分探索を行うだけで全ての配列を探索するのに近い結果が得られる。 フラクショナル・カスケーディング（英語版） は、複数の整列配列に対して同じ要素を探索する際に、二分探索によって高速な探索を行う手法である。配列を個別に探索する場合、${\textstyle k}$ ノイズのある二分探索では、比較処理が一定の確率で誤った結果を返す。 ノイズのある二分探索 (noisy binary search) は配列要素の比較に確実性がない問題に対するアルゴリズムであり、各回の比較結果が一定の確率で誤っているにもかかわらず所定の正確さで目標値の位置を見つけ出すことができる。この種の手法はいずれも、平均して少なくとも ${\displaystyle (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}}$; book version . Stroustrup, Bjarne (2013). The C++ programming language (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2  外部リンク NIST Dictionary of Algorithms and Data Structures: binary search Comparisons and benchmarks of a variety of binary search implementations in C Archived 25 September 2019 at the Wayback Machine. 表 話 編 歴 アルゴリズム ソート 比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート 探索 リスト 線形探索 二分探索 木・グラフ 幅優先探索 最良優先探索 均一コスト探索 A* 深さ優先探索 反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 ビームサーチ 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法 最短経路問題 ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法 最小全域木 プリム法 クラスカル法 最大フロー問題 最小カット問題 フォード・ファルカーソン法 エドモンズ・カープ法 線型計画問題 シンプレックス法 カーマーカー法 順序統計量 選択アルゴリズム クイックセレクト 中央値の中央値 計算幾何学 凸包アルゴリズム 種類 近似アルゴリズム 乱択アルゴリズム 並列アルゴリズム 分散アルゴリズム 可積分アルゴリズム その他 分割統治法 動的計画法 貪欲法 累積和 アルゴリズム作曲法 カテゴリ 英和和英テキスト翻訳 >> Weblio翻訳 英語⇒日本語日本語⇒英語    >> 「二分検索」を含む用語の索引  二分検索のページへのリンク 辞書ショートカット 1 デジタル大辞泉 2 ウィキペディア カテゴリ一覧 全て ＋ ビジネス ＋ 業界用語 ＋ コンピュータ ＋ 電車 ＋ 自動車・バイク ＋ 船 ＋ 工学 ＋ 建築・不動産 ＋ 学問 ＋ 文化 ＋ 生活 ＋ ヘルスケア ＋ 趣味 ＋ スポーツ ＋ 生物 ＋ 食品 ＋ 人名 ＋ 方言 ＋ 辞書・百科事典 すべての辞書の索引 あいうえお かきくけこ さしすせそ たちつてと なにぬねの はひふへほ まみむめも やゆよ らりるれろ わをん がぎぐげご ざじずぜぞ だぢづでど ばびぶべぼ ぱぴぷぺぽ ＡＢＣＤＥ ＦＧＨＩＪ ＫＬＭＮＯ ＰＱＲＳＴ ＵＶＷＸＹ Ｚ １２３４５ ６７８９０ 記号 Weblioのサービス 英会話コラム Weblio英会話 英語の質問箱 語彙力診断 スピーキングテスト 「二分検索」の関連用語 1 二分探索 デジタル大辞泉 34% ||||| 2 計算の複雑性 ウィキペディア小見出し辞書 10% ||||| 3 データベースエンジン 百科事典 4% ||||| 4 二進対数 百科事典 4% ||||| 二分検索のお隣キーワード 二分ヒープ 二分久男 二分心 二分探索 二分探索木 二分木 二分検索 二分決定図 二分法 二分脊椎症 二分膝蓋骨 二分論 二分金 検索ランキング 英和和英テキスト翻訳 >> Weblio翻訳     英語⇒日本語 日本語⇒英語     二分検索のページの著作権 Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。     (C)Shogakukan Inc. 株式会社 小学館 All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの二分探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。 ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典 ご利用にあたって ・Weblio辞書とは ・検索の仕方 ・ヘルプ ・利用規約 ・プライバシーポリシー ・サイトマップ 便利な機能 ・ウェブリオのアプリ ・画像から探す お問合せ・ご要望 ・お問い合わせ 会社概要 ・公式企業ページ ・会社情報 ・採用情報 ウェブリオのサービス ・Weblio 辞書 ・類語・対義語辞典 ・英和辞典・和英辞典 ・Weblio翻訳 ・日中中日辞典 ・日韓韓日辞典 ・フランス語辞典 ・インドネシア語辞典 ・タイ語辞典 ・ベトナム語辞典 ・古語辞典 ©2025 GRAS Group, Inc.RSS      ログイン ※半角英数字、6文字以上、32文字以内で入力してください ログイン パスワードを忘れた方はこちらから 別サービスのアカウントで登録・ログイン アカウントをお持ちでない方 新規会員登録（無料）