【基本情報】独学マラソン 線形探索 Day 28

この記事は自分用の備忘録です。

線形探索（linear search）とは

端から順番に探す方法
配列[30, 60, 90]があって、60を探すときに
1番目：30 60ではない
2番目：60 60と一致　終了
みたいな感じ

linearSearch.ts

type SearchParams = {
  array: number[];
  target: number;
};

function linearSearch({ array, target }: SearchParams): number {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}

でもこれだと、毎回ループの最初に配列の長さをチェックしてしまう
現代のCPU的には条件分岐をなるべく削減するほうがいいらしい

そこで、ループに入る前に配列の最後にスプレッド構文でターゲットの値を追加しておいて、無限ループをさせると効率良く探索できる

セントリー法と呼ばれている

sentinelLinearSearch.ts

type SearchParams = {
  array: number[];
  target: number;
};

function linearSearchWithSentinel({ array, target }: SearchParams): number {

  const sentinelArray = [...array, target];

  let i = 0;
  while (true) {
    if (sentinelArray[i] === target) {
      return i < array.length ? i : -1;
    }
    i++;
  }
}

これなら値が見つかったら即returnするし
値が元の配列に存在しなくても、最後に追加した分が必ず見つかるから
-1がreturnされる

例えば、配列のサイズが1兆（10^12）で毎回条件分岐（i < array.length）を行うと、1回ごとの処理が少なくても、その影響が累積して大きくなってしまう

配列をループで回すときにはわずかな処理も莫大になるかもしれないので気をつけよう

感想

無駄がないコードって気持ちいい

参考