概要
前回はリニアサーチを完成させました(前回の記事)。今回から新しいアルゴリズム、バイナリーサーチを順序立てて解説します。日本語では２分探索法とも言います。横文字だとかっこよく聞こえますが２分探索なので字の通りデータを半分に分けて探索します。以下がイメージです。
バイナリーサーチは探したい値がデータ全体を中心値で2分割した時、中央の配列が探したい値かどうか、そうでなければ中央の配列と比較して大きいグループか小さいグループにあるのかを判定し、再度2分して値が見つかるまで繰り返します。
1つ注意点としてデータの順番がランダムの場合は使えません。その場合は一度ソート(昇順、もしくは降順に整列)してから使用します。注意してください。
まずは資料の手順1、データ全体を2分するコードをCとVBAで書きます。
コード
#include <stdio.h>
#define NUM 100
int main()
{
int arr[NUM];
int val=42; //探したい値
int center; //中央要素
int head=0; //先頭要素
int tail=NUM-1; //末端要素
//配列に値を格納
for(int i=0;i<NUM;i++)
arr[i]=i+1;
center=(tail-head)/2; //真ん中の要素数を計算
if(arr[center]==val) //値をみつけた時
printf("%s\n","true");
else if(val<arr[center]) //値が前半グループにある時
printf("%s\n","first half");
else //値が後半グループにある時
printf("%s\n","latter half");
return 0;
}Option Explicit
Const NUM As Integer = 99
Sub searchBinary()
Dim arr(NUM) As Integer
Dim val As Integer: val = 42 '探したい値
Dim center As Integer
Dim head As Integer: head = 0 '先頭要素
Dim tail As Integer: tail = NUM '末端要素
Dim i As Integer
'配列格納ループ
For i = 0 To NUM
arr(i) = i + 1
Next i
center = Int((tail - head) / 2) '真ん中の要素数を計算
If (arr(center) = val) Then '値をみつけた時
Debug.Print "true"
ElseIf (val < arr(center)) Then
Debug.Print "first half" '値が前半グループにある時
Else
Debug.Print "latter half" '値が後半グループにある時
End If
End Sub コードを実行する前にポイントを解説します。まずは1回目の探索を行います。真ん中の配列を中心に配列を2分します。計算式99-(0-1)つまり99+1で100です。これは配列の個数を指します。それを2で割ると真ん中の要素が求められます。割り切れない場合は余りは切り捨てます。
それでは実行してみましょう。見つけたい値が前半部部分は(first half)にあると出力されたと思います。今回は1回目の2分探索を行い、前後どちらのブロックに値があるか表示しました。次回は2回目の2分探索を行い、値がどこにあるか更に絞り込みます。