今回は2分探索法のアルゴリズムについて、JavaScript でコードをみていきたいと思います。
2分探索法とは
まず、配列などデータの集まったものから特定のデータを探し出すことをデータの探索といい、探索範囲を半分に繰り返し絞り込んでいく方法を2分探索法といいます。
2分探索法を使うには、データが昇順か降順に整列されている必要があります。
たとえば、以下のような id と名前のデータがあったとします。
15 | 佐藤 |
23 | 鈴木 |
34 | 高橋 |
49 | 田中 |
51 | 伊藤 |
68 | 渡辺 |
72 | 山本 |
87 | 中村 |
93 | 小林 |
104 | 加藤 |
この中から id が72である人物の名前を検索するとしましょう。
データが10件なので、
(1+10)÷2(小数点切り捨て)=5となります。
5番目の id をみると51であるため、目的のデータはこれよりも後ろにあることがわかります。
したがって6番目以降のデータに注目し、同じ処理を繰り返します。
68 | 渡辺 |
72 | 山本 |
87 | 中村 |
93 | 小林 |
104 | 加藤 |
(6+10)÷2=8
8番目の id をみると87であるため、目的のデータはこれよりも前にあることがわかります。
したがって、7番目より前のデータに注目します。
68 | 渡辺 |
72 | 山本 |
(6+7)÷2(小数点切り捨て)=6
6番目の id をみると68であるため、目的のデータはこれよりも後ろにあることがわかります。
したがって、残った7番目のデータをみると id が72であり、名前「山本」が取得できました。
このように半分ずつ範囲を絞っていくような流れになります。
実装
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('該当データなし');
}
参考書
コメント