【探索】

配列は探すのが遅いと前回触れました。この弱点を解決する道具が、2つあります。1つ目はハッシュテーブルでした。そして2つ目、二分探索です。この章で、今まで注釈の顔でちらちら登場してきたO記法を、正式に整理します。

線形探索

まず、今まで使ってきた探し方の正体から。includesやindexOfは、内部で先頭から1件ずつ順に確認していました。この探し方には線形探索という名前がついています。自分で書くとこうなります。

const linearSearch = (arr: number[], target: number): number => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;   // 見つけた位置を返す
  }
  return -1;   // 最後まで見ても無ければ -1
};

indexOfの中身は実質これです。シンプルで、どんな配列にも使えるのが長所。短所は知っての通り、最悪で全件確認、つまりO(n)です。

二分探索

ここからが本題です。もし配列が昇順に並んでいるなら、劇的に速い探し方ができます。

1〜100の数当てゲームを考えてください。相手の数を当てるゲームです。ヒントは「もっと大きい/小さい」だけ。1から順に聞く人はいません。50?(もっと大きい)→75?(もっと小さい)→62?…と、真ん中を聞いて、半分を捨てるはずです。これなら100個の候補も7回で必ず当たります。

この探し方が二分探索です。並んだ配列の 真ん中を見て、目当てより小さければ右半分へ、大きければ左半分へ、 1回の確認で候補が半分になる。以下でコードにします。