はじまり

基本情報の探索アルゴリズムについて勉強したある日、
2分探索法の問題に出会いました。

問題

昇順に整列されたn個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。

ア：log2n　イ：（log2n +1)/2　ウ：n　エ：n2


即座に「分からない！」と思い、選択肢の解答に直行すると、
解答はア：log2n

うん、解答見ても分からんとなりました。（お恥ずかしい限りです。汗）

以下、主に自分の備忘録目的で、
logって何？な状態から調べた内容になります。

2分探索法について

茶番はこの辺にしまして、
まずは2分探索法について簡単に解説します。

2分探索法とは、一言でいうと、
「データの中央値」と「探したいデータ」を比較し、探索範囲を1／2ずつ狭めていく手法です。

以下の図を用いて説明します。

データが、小さいもの順の「1から4」で構成されてるとします。
今回はこの中から「2」を探したいです。

この時、2分探索法では最初に、「データの中央値（2.5）」と「探したい数（2）」を比較します。
そして、今回は「探したい数（2）」が「データの中央値（2.5）」より小さいです。

すると、
探したい数は「2.5」より小さいデータの「1から2」の間にあることになります。
あとは、同じことを繰り返すだけ、
次は「探したい数（2）」が「データの中央値（1.5）」と比べて大きいか小さいかを比べて、今回は大きいということで、「2」を探すことができます。

log2Xってなんだ？

logは、対数を表すことができます。
対数とは、何乗したら何になるかを表すものです。

仮に（XY＝Z）というXのY乗がZという式があった場合、
対数では、Y＝logXZと表すことができます。
すると、Y＝log2Xとは2のY乗がXということになります。

問題の解答

では、先ほどの問題に戻りましょう。
昇順に整列されたn個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。

ア：log2n　イ：（log2n +1)/2　ウ：n　エ：n2

この問題の解答はlog2nでした。
これを先ほどのY＝logXZの時、XのY乗がZというルールに当てはめると、

比較回数=log2n（2比較回数＝n）
つまり
2の比較回数乗がn（データの個数）ということになります。

これが本当なのか。実際に見てみましょう。

まずは、比較回数が1回のとき、
2=nで
データの個数は2になります。

実際のところ下記のように、1回比較するだけで探したい数が見つかるのはデータの個数は2つあるときになります。

同じように考えると、比較回数が2回のとき、
4=nで、
データの個数は4になります。

実際の下記の図を見ても、比較回数2回で探したい数を探すのにデータ数は4つあります。

中にはデータ数が奇数になったりすると、log2n＋1になるパターンもありますが、
今回の問題では、おおよその比較回数が何かを選択肢から選ぶパターンなので、
ア：log2nとなるわけですね。