今回は線形探索法のアルゴリズムについて、JavaScript でコードをみていきたいと思います。
線形探索法とは
まず、配列などデータの集まったものから特定のデータを探し出すことをデータの探索といい、データを１件目から順々に比較して探していく方法を線形探索法といいます。
たとえば、以下のような id と名前のデータがあったとします。
| 1 | 佐藤 |
| 2 | 鈴木 |
| 3 | 高橋 |
| 4 | 田中 |
| 5 | 伊藤 |
| 6 | 渡辺 |
| 7 | 山本 |
| 8 | 中村 |
| 9 | 小林 |
| 10 | 加藤 |
この中から「山本」の id を検索するとしましょう。
まず１件目のデータを取り出して、その名前が検索名と一致しているか確認し、
違っていたら２件目、３件目と順々に探していきます。
そして７件目で一致し、id が７であることがわかります。
実装
let datas = [
{id: 1, name: '佐藤'},
{id: 2, name: '鈴木'},
{id: 3, name: '高橋'},
{id: 4, name: '田中'},
{id: 5, name: '伊藤'},
{id: 6, name: '渡辺'},
{id: 7, name: '山本'},
{id: 8, name: '中村'},
{id: 9, name: '小林'},
{id: 10, name: '加藤'}
];//この中から探す
let searchName = '山本';//検索する名前
for (let i = 0; i < datas.length; i++) {
if (searchName == datas[i].name) {
console.log(`id:${datas[i].id}`);//「id:7」と表示
break;
}
if (i == datas.length-1) {
console.log('該当データなし')
}
}解説
目的のデータが見つかったら、
break;としてループを強制終了させています。
また、最後まで目的のデータが見つからなかった場合は以下のようにして例外処理をしています。
if (i == datas.length-1) {
console.log('該当データなし')
}
これでも線形探索法は実装できますが、以下のように修正し、 if 文をループの外に置くことで if 文の処理を一回だけに減らすことができます。
let datas = [
{id: 1, name: '佐藤'},
{id: 2, name: '鈴木'},
{id: 3, name: '高橋'},
{id: 4, name: '田中'},
{id: 5, name: '伊藤'},
{id: 6, name: '渡辺'},
{id: 7, name: '山本'},
{id: 8, name: '中村'},
{id: 9, name: '小林'},
{id: 10, name: '加藤'}
];//この中から探す
let searchName = '山本';//検索する名前
datas.push({id: datas.length+1, name: searchName});
let i = 0;
while(searchName != datas[i].name) {
i++
}
if (i == datas.length-1) {
console.log('該当データなし');
}else{
console.log(`id:${datas[i].id}`)
}
ポイントは、配列の最後に検索データを追加することです。
datas.push({id: datas.length+1, name: searchName});
これによって、配列の中身は以下のようになっています。
let datas = [
{id: 1, name: '佐藤'},
{id: 2, name: '鈴木'},
{id: 3, name: '高橋'},
{id: 4, name: '田中'},
{id: 5, name: '伊藤'},
{id: 6, name: '渡辺'},
{id: 7, name: '山本'},
{id: 8, name: '中村'},
{id: 9, name: '小林'},
{id: 10, name: '加藤'},
{id: 11, name: '山本'}//これが追加される
];
そして、while 文で目的のデータが何番目かを調べます。
let i = 0;
while(searchName != datas[i].name) {
i++
}
もしも目的のデータがない場合は、配列の一番最後に追加したデータが必ず引っかかるようになっているため、以下の if 文が true になり「該当データなし」が表示されます。
if (i == datas.length-1) {
console.log('該当データなし');
}
参考書
コメント