【アルゴリズム(JS実装)】Linear Search
どうも、わくばです!
Sortに関してはある程度有名なものをやり終えたので、Searchに入ろうと思います。
今日はLinear Searchです。一番簡単なサーチだと思います。
コードはこんな感じです。
function linearSearch(array, value){ let results = [] for(let i = 0; i < array.length; i++){ if(arr[i] === value){ results.push(i) } } return results ? results : -1 } console.log(linearSearch([13,6,7,9,6,8,9,4,1,3], 9)) >>>[ 3, 6 ]
9を探すテストを実行しています。9があるキーは3と6のようですね。あっています。
オーダーは最もシンプルな\(O(n)\) です。サーチの中でも効率の悪い方という記述がありましたが、他のもやってみないとイマイチピンときません。ソートで
勉強した経験からだと、二分するタイプなら\(O(logn)\)でいけそうなのでそれよりは確かに遅いかもしれませんね。
ちなみにjavascriptのArrayオブジェクトに実装されているfilter() メソッドのソースコードを確認したら、どうやらあLinear Sortのアルゴリズムを用いているようでした。ただし返すのはキーではなくでそのままvalueという違いはありました。
自分が普段使っているメソッドも、勉強したアルゴリズムで実装されているのを見るとかなり楽しいですね。
では。