仕様
前回からバイナリーサーチというアルゴリズムについて解説しています(前回の記事)。今回はその続きで2回目の探索について記載しました。以下資料がバイナリーサーチの概要で、今回は2を行います。
コード
前回のコードは値が２分した配列の前半グループか後半グループにあるか出力しました。今回は真ん中の要素数を出力します。以下がコードです。
#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;
//1回目
center=(tail-head)/2; //真ん中の要素数を計算
printf("%s%d\n","1 time:center=",center);
if(arr[center]==val) //値をみつけた時
printf("%s\n","true");
else if(val<arr[center]) //値が前半グループにある時
tail=center-1; //配列末尾の要素数変更
else //値が後半グループにある時
head=center+1; //配列先頭の要素数変更
//２回目
center=(tail-head)/2; //真ん中の要素数を計算
printf("%s%d\n","2 time:center=",center);
if(arr[center]==val) //値をみつけた時
printf("%s\n","true");
else if(val<arr[center]) //値が前半グループにある時
tail=center-1; //配列末尾の要素数変更
else //値が後半グループにある時
head=center+1; //配列先頭の要素数変更
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
'1回目
center = Int((tail - head) / 2) '真ん中の要素数を計算(Int関数で小数点切り捨て)
Debug.Print "1 time:center=" + CStr(center) '値が前半グループにある時
If (arr(center) = val) Then '値をみつけた時
Debug.Print "true"
ElseIf (val < arr(center)) Then
tail = center - 1 '配列末尾の要素数変更
Else
head = center + 1 '配列先頭の要素数変更
End If
'2回目
center = Int((tail - head) / 2) '真ん中の要素数を計算(Int関数で小数点切り捨て)
Debug.Print "2 time:center=" + CStr(center) '値が前半グループにある時
If (arr(center) = val) Then '値をみつけた時
Debug.Print "true"
ElseIf (val < arr(center)) Then
tail = center - 1 '配列末尾の要素数変更
Else
head = center + 1 '配列先頭の要素数変更
End If
End Sub 今回のポイントは値が前半にある場合はtailの値、つまり配列の最後尾の値を変更します。計算式はcenter-1です。ここで注意点として、centerの値をtailに代入してしまうとtailの配列を2回探索することになるので必ずマイナス1をします。一方後半にある場合はheadにcenter+1の値を代入します。言葉ではイメージしにくい場合は上記資料の絵を見ながらイメージすると理解しやすいと思います。コードを実行してみると、1回目は49、2回目は24と出力されたと思います。
次回は3回目の検索を行います。