探索のアルゴリズム
「配列」から目的とする値を見つけ出すことを「探索」とよびます。ここでは、２種類の「探索」についてのアルゴリズムをみていきます。
線形探索
「線形探索」は、配列を端から順に確認していくアルゴリズムです。
たとえば、以下の配列 A があるとします。
A = [ 2, 4, 5, 10, 1, 8, 3 ]
この配列から 5 を見つけるために、端から見ていくと、 2, 4, 5 と 3回の探索で見つけることができます。探索回数について、もう少し詳しくみていくと、
最小探索回数は 1回（2を探索する場合）
最大探索回数は 7回（3を探索する場合）となります。
よって、これから平均探索回数を算出すると (1 + 7) / 2 = 4回となります。
ここで、7 は配列の要素数からきていますので、これを n とすれば、
「線形探索」の平均探索回数は、(1 + n) / 2 回 と表すことができます。
二分探索
上述の「線形探索」よりも探索回数を減らすために工夫したのが「二分探索」です。
まず、二分探索は探索する配列を事前に昇順（厳密には降順でも可能）にしておく必要があります（昇順とは小さい順で、降順とは大きい順です）。
ざっくりと、このアルゴリズム概要を言えば「半分ずつ見ていこう！」といった感じです。
それでは、以下の配列があり、その中から線形探索では 8回の探索が必要になる 11 を見つけることにします。
A = [ 1, 2, 3, 4, 5, 8, 10, 11, 15 ]
「二分探索」では、まず配列の真ん中に位置する値に注目します。配列 A において真ん中に位置する値は 5 です。
目的とする値 11 は その 5 よりも大きいため、今見ている位置より後ろにあることが分かります（これが昇順になっている必要があることの意味です）。
次に、配列 A の 5 の次の要素である 8 を起点とした場合の、真ん中に位置する値に注目します。部分配列 [ 8, 10, 11, 15 ] の真ん中に位置する値は、要素数が偶数なので10 または 11 です。この場合は前側と後側のどちらに注目するかは任意に決めれば良いです（そのルールは一貫して適用する必要はあります）。ここでは前側にすることにして、10 は 11よりも小さいため、また、10 の次の要素を起点に探索します。
次の部分配列は [11, 15] となり、この部分配列の真ん中に位置する値は（要素数が偶数で、その場合は前側を採用することにしていたので） 11 です。ここで 11が見つかりました。
以上のように「二分探索」をすることで、探索回数が 3回 になりました。「線形探索」の8回よりも少なくなりましたね！
また、探索の過程で探索対象とする配列の要素数は、9 → 4 → 2 となっていました。これは、探索をすすめるにつれておおよそ半分になっていますね。これが上で「半分ずつ見ていこう！」と言っていた意味です。
探索回数についてもう少し詳しくみていくと、
要素数を N として、探索回数を n とします。
N を 2 で n 回割れば目的とする要素の数 1 が残るので、
N ／ 2n = 1 と書けます。 （2n = 2（1回目） x 2（2回目）x ・・・ x 2（n回目）という意味ですね。）
この式の両辺に、2n を掛けると、
N ＝ 2n となりますね。
これに、２を底とする対数をとれば、
log2 2n = log2 N となり、左辺を整理して、
n = log2 N となりました！ これが「2分探索」の平均探索回数です。ちなみに、最大探索回数は 配列数の偶奇により + 1 回が生じる場合があるので、 log2 N + 1 回となります。
今一度、「線形探索」と「二分探索」の平均探索回数を比較すると、
N = 10 の時、線形探索：5.5回 二分探索：3.32回
N = 100 の時、線形探索：50.5回 二分探索：6.64回
N = 10000 の時、線形探索：5000.5回 二分探索：13.3回
となります。「二分探索」はかなりすごいですよね！
ちなみに、配列が昇順または降順になっていない場合は、揃える（ソートする）ために 別途 N log2 N 回の計算が必要になります。
