今回は２分探索法のアルゴリズムについて、JavaScript でコードをみていきたいと思います。
２分探索法とは
まず、配列などデータの集まったものから特定のデータを探し出すことをデータの探索といい、探索範囲を半分に繰り返し絞り込んでいく方法を２分探索法といいます。
２分探索法を使うには、データが昇順か降順に整列されている必要があります。
たとえば、以下のような id と名前のデータがあったとします。
| 15 | 佐藤 |
| 23 | 鈴木 |
| 34 | 高橋 |
| 49 | 田中 |
| 51 | 伊藤 |
| 68 | 渡辺 |
| 72 | 山本 |
| 87 | 中村 |
| 93 | 小林 |
| 104 | 加藤 |
この中から id が７２である人物の名前を検索するとしましょう。
データが１０件なので、
（１+１０）÷２（小数点切り捨て）＝５となります。
５番目の id をみると５１であるため、目的のデータはこれよりも後ろにあることがわかります。
したがって６番目以降のデータに注目し、同じ処理を繰り返します。
| 68 | 渡辺 |
| 72 | 山本 |
| 87 | 中村 |
| 93 | 小林 |
| 104 | 加藤 |
（６+１０）÷２＝８
８番目の id をみると８７であるため、目的のデータはこれよりも前にあることがわかります。
したがって、７番目より前のデータに注目します。
| 68 | 渡辺 |
| 72 | 山本 |
（６+７）÷２（小数点切り捨て）＝６
６番目の id をみると６８であるため、目的のデータはこれよりも後ろにあることがわかります。
したがって、残った７番目のデータをみると id が７２であり、名前「山本」が取得できました。
このように半分ずつ範囲を絞っていくような流れになります。
実装
let datas = [
{id: 15, name: '佐藤'},
{id: 23, name: '鈴木'},
{id: 34, name: '高橋'},
{id: 49, name: '田中'},
{id: 51, name: '伊藤'},
{id: 68, name: '渡辺'},
{id: 72, name: '山本'},
{id: 87, name: '中村'},
{id: 93, name: '小林'},
{id: 104, name: '加藤'}
];//この中から探す
let searchId = 72;//検索する名前
let low = 0;
let high = datas.length-1;
while (low <= high) {
let middle = Math.floor((low+high)/2);
if (searchId > datas[middle].id) {
low = middle + 1;
}else if(searchId < datas[middle].id) {
high = middle - 1;
}else{
console.log(`${searchId}:${datas[middle].name}`);//「72:山本」と表示
break;
}
if (low > high) {
console.log('該当データなし');
}
}解説
low ~ high 番目のデータが検索の対象となります。
low と high の中間である middle 番目のデータの id と検索 idのどちらが大きいかによって low や high を修正します。
一致した場合はコンソールに表示しループを終えます。
if (searchId > datas[middle].id) {
low = middle + 1;
}else if(searchId < datas[middle].id) {
high = middle - 1;
}else{
console.log(`${searchId}:${datas[middle].name}`);//「72:山本」と表示
break;
}
また、検索 id が配列に存在しない場合は自動的に low が high よりも大きくなるため、以下のように例外処理をしています。
if (low > high) {
console.log('該当データなし');
}
参考書
コメント