二分探索のソースを表示
←
二分探索
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''二分探索'''（にぶんたんさく、BS;Binary Search）とは[[検索]]の[[アルゴリズム]]の一つ。'''二分検索'''、'''バイナリサーチ'''ともいう。 [[ソート]]済みの[[リスト]]や[[配列]]に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。 大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。 n個のデータがある場合、時間計算量は<math>O(\log_2 n)</math>である（[[O記法]]）。 n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。 ==例== 具体例を示す。 ===データが見つかる例=== 下記のような配列から'''''25'''''を探しだすことを考える。なお、同一のデータは無いものとする。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>'''''25'''''</td><td>28</td></tr> </table> 結果欄を設け、目的のデータがあるか否か不明な部分を「?」、データを調べた上で目的のデータが無いとわかった部分を「'''×'''」、データを調べるまでもなく目的のデータが無い部分を「×」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>'''''25'''''</td><td>28</td></tr> <tr><th>結果 </th><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><tr> </table> まず、配列の中央の位置を求めると、(1+10)/2=5 :（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ） 位置5のデータは12なので「'''×'''」、位置1～4まではデータを調べなくても「×」とわかる。目的のデータは位置6～10にあるかもしれない。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>'''''25'''''</td><td>28</td></tr> <tr><th>結果 </th><td>×</td><td>×</td><td>×</td><td>×</td><td>'''×'''</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td> ?</td><tr> </table> 位置6～10の中央の位置は、(6+10)/2=8 位置8のデータは22なので「'''×'''」、位置6～7までは「×」とわかる。目的のデータは位置9～10にあるかもしれない。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>'''''25'''''</td><td>28</td></tr> <tr><th>結果 </th><td>×</td><td>×</td><td>×</td><td>×</td><td>'''×'''</td><td>×</td><td>×</td><td>'''×'''</td><td> ?</td><td> ?</td><tr> </table> 位置9～10の中央の位置は、(9+10)/2=9 位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、同一のデータは存在しないという想定なので「×」としてよい。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>'''''25'''''</td><td>28</td></tr> <tr><th>結果 </th><td>×</td><td>×</td><td>×</td><td>×</td><td>'''×'''</td><td>×</td><td>×</td><td>'''×'''</td><td>'''○'''</td><td>×</td><tr> </table> ===データが見つからない例(1)=== 下記のような配列から'''''4'''''を探しだすことを考える。なお、同一のデータは無いものとする。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>25</td><td>28</td></tr> </table> まず、配列の中央の位置を求めると、(1+10)/2=5 :（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ） 位置5のデータは12なので「'''×'''」、位置6～10まではデータを調べなくても「×」とわかる。目的のデータは位置1～4にあるかも知れない。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>25</td><td>28</td></tr> <tr><th>結果 </th><td> ?</td><td> ?</td><td> ?</td><td> ?</td><td>'''×'''</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><tr> </table> 位置1～4の中央の位置は、(1+4)/2=2 位置2のデータは3なので「'''×'''」、位置1も「×」とわかる。目的のデータは位置3～4にあるかも知れない。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>25</td><td>28</td></tr> <tr><th>結果 </th><td>×</td><td>'''×'''</td><td> ?</td><td> ?</td><td>'''×'''</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><tr> </table> 位置3～4の中央の位置は、(3+4)/2=3 位置3のデータは5なので「'''×'''」。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>25</td><td>28</td></tr> <tr><th>結果 </th><td>×</td><td>'''×'''</td><td>'''×'''</td><td>×</td><td>'''×'''</td><td>×</td><td>×</td><td>×</td><td>×</td><td>×</td><tr> </table> ===データが見つからない例(2)=== 下記のような配列から'''''29'''''を探しだすことを考える。なお、同一のデータは無いものとする。 <table border="1" cellpadding="2" > <tr><th>位置</th><th> 1</th><th> 2</th><th> 3</th><th> 4</th><th> 5</th><th> 6</th><th> 7</th><th> 8</th><th> 9</th><th>10</th></tr> <tr><th>データ </th><td> 1</td><td> 3</td><td> 5</td><td>11</td><td>12</td><td>13</td><td>17</td><td>22</td><td>25</td><td>28</td></tr> </table> データの全体の一番右側が29より小さいので、データが見つからないという結果になる。 ==関連項目== *[[二分法]] :（二分探索のようなアイデアで方程式の近似解を求める方法） [[Category:検索アルゴリズム|にふんたんさく]] [[ar:ديكوتومية]]
二分探索
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報
