【JavaScriptでアルゴリズム】データの探索(2分探索法)

アルゴリズム

今回は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('該当データなし');
  } 





参考書

コメント

コンタクトフォーム

    タイトルとURLをコピーしました