2分探索について

計算量について


2分探索の計算量は$O(log_{2} x)$ となり、対数時間となる。

前提条件


2分探索は対象の配列が既にソート済みとなっていることが条件となる。

考え方


例えば8つの数字を含む配列から7という数値を見つけようとした場合、順番に半分に分割していく。

この時に配列の数は8なので計算量は$O(log_{2} 8)$となる。最大の探索数は3となる。

実装


例えば1 2 4 8 9 10 15という配列から9のインデックスを取得しようとすると下記の手順で実装する。

まず、3つの変数を用いる。ここでは仮にheadmiddletailとする。

  • head: 探索範囲の頭のインデックス
  • tail: 探索範囲の最後のインデックス
  • middle: 探索範囲の真ん中のインデックス

今回は要素数が7なのでそれぞれの初期値は下記のようになる。

  • head: 0
  • tail: 6
  • middle: 3

これらを用いて順に実装する。

  1. 配列の要素数を取得する
  2. 探索範囲の真ん中のインデックスをmiddle変数に格納する
  3. middleのインデックスの値(4)と欲しい値(9)を比較する
  4. 欲しい値の方が大きいので探索範囲を変更する
    • 欲しい値の方が大きければheadの値をmiddle+1したものにする
    • 欲しい値の方が小さければtailの値をmiddle-1したものにする

後はみつかるまで2~4を繰り返す。

JavaScriptでの実装


前例をJavaScript(Node.js)で実装するとこうなる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function main() {
const x = 9;
const list = [1 2 4 8 9 10 15]

let head = 0;
let tail = list.length - 1;
let middle = 0;

while (head <= tail) {
middle = Math.floor((head + tail) / 2);
if (x === list[middle]) {
console.log(middle);
process.exit();
}
if (x > list[middle]) {
head = middle + 1;
} else {
tail = middle - 1;
}
}
console.log("Not found");
}

おわり。

参考書籍


なっとく! アルゴリズム