アルゴリズム「線形探索」「二分探索」をやってみる

データを扱う際、必要なのは適したアルゴリズムです。
少しのデータならば差異はありませんが、多くなってくると時間がかかる、パフォーマンスが悪いなど顕著になってきます。

アルゴリズムの線形探索、二分探索についてJavaScriptを用いて説明します。

アルゴリズムとは

アルゴリズムとは、ある特定の問題を解く手順を、単純な計算や操作の組み合わせとして明確に定義したもの。
https://e-words.jp/w/アルゴリズム.html

線形探索

リニアサーチとも呼ばれます。

このアルゴリズムは、「配列を直線的に探索し処理する」ことが行われます。
つまり、先頭から順番に必要な値を探す処理を行っているわけです。

以下、例として数値配列から見つける数値のインデックスを出力します。
見つからなければ-1を返します。

const numbers = [...Array(10000).keys()].map((_, i) => i)
const searchValue = 9999

let index = -1

for (let i = 0; numbers.length > i; i++) {
  if (numbers[i] === searchValue) {
    index = i
    break
  }
}

console.log(index)

配列の端から順番に処理しているのかわかります。
これがさらに配列が多くなってくると顕著に現れます。

二分探索

バイナリサーチとも呼ばれます。

こちらは、中央値を定め、左辺右辺のどちらに属しているかを確認して、また中央値...をというような探索を行います。

const numbers = [...Array(10000).keys()].map((_, i) => i)
const searchValue = 9999

let index = -1
let left = 0
let right = numbers.length - 1

while (left <= right) {
  const middle = Math.floor((left + right) / 2)

  if(numbers[middle] === searchValue) {
      index = middle
      break
  } else if (numbers[middle] < searchValue){
      left = middle + 1
  } else {
      right = middle -1
  }
}

console.log(index)

半分ずつ割っていくので、探索値までの到達スピードが速くなります。
配列が100000, 1000000...となればなるほどこのアルゴリズムが重要になっていきます。

最後に

線形探索は知っていましたが二分探索は知らなかったのが本音です。
パフォーマンスを意識したプログラミングを心がけていきたいところです。