Binary Searchを用いた整数探索の実例

Binary Searchとは

ある範囲の中にある、ある数を、中間値で範囲を限定しながら探索するアルゴリズムです。
今回はその実例をお見せしますのでご覧ください

実例

1から8まで整数があります。
その中から今回は7を探索します。($T=7$とします。)
1, 2, 3, 4, 5, 6, 7(T), 8
ステップ数を$i$(0始まり)
最初の数をS, 最後の数をE、その中間値（切り下げ)を$g_i$とすると
$i = 0: $
$\ S = 1$
$\ E = 8$
$\ g_0 = floor(\frac{S+E}{2}) = 4$

つまり、
$i=0$の結果
1(S), 2, 3, 4(g), 5, 6, 7(T), 8 (E)
$g_i$とTを比較し、もし一致していればそこで終了。今回は一致していないので続行します。

$i=1: $
$g_i < TならS = g_i$
$g_i > TならE = g_i$
と新しくおきます。
今回は$g_0 = 4 < T$ = 7なので
新しく$S = 4$になります。
新しい$g_1$は
$g_1 = floor(\frac{S+E}{2}) = floor(\frac{4+8}{2}) = 6$
よって
$i=1$の結果
4(S), 5, 6(g), 7(T), 8 (E)
$g_1 = 6 \neq T = 7$なので続行。

$i=2: $
$g_0 = 6 < T$ = 7なので$S = g_1 = 6$
$g_2 = floor(\frac{S+E}{2}) = 7$
$i = 2$の結果
6(S), 7(g, T), 8 (E)
$g_2 = T = 7$より、無事探索終了です！

まとめ

今回は3回で探索が終わりました。

私は、これは8個の整数の中からbinary searchを使って探索する際の最大ステップ数になると考えております。
ざっくりと説明すると、探索数の最大値は$O(log_2N)$なるからだと思っております。
なぜならば、一回探索するたびに、探索範囲が大体半分ずつ削れていくからです。（各ステップのグレーの部分をご覧ください。)

厳密な説明は他所にお譲りします。