n のバイナリ表現に従って、n 個の要素を格納するために、それぞれの長さが 2^k の複数の配列を使用するという考え方です。
上記のデータ構造では、SEARCH は各配列のバイナリ検索のシーケンスによって実行されます。INSERT は、空の配列に到達するまで、同じ長さの配列の一連のマージによって実行されます。
詳細:長さ 2^k の垂直配列があり、その配列の各ノードに長さ 2^k の水平配列が接続されているとします。
つまり、垂直配列の最初のノードには、長さ 2^0=1 の水平配列が接続され、垂直配列の 2 番目のノードには、長さ 2^1= 2 の水平配列が接続されます。したがって、挿入は最初の水平配列で最初に実行され、2 番目の挿入では最初の配列は空になり、2 番目の水平配列は 2 つの要素でいっぱいになり、3 番目の挿入では 1 番目と 2 番目の配列水平になります。配列が満たされているなどです。次のように、検索と挿入の通常のバイナリ検索を実装しました。
int main()
{
int a[20]= {0};
int n, i, j, temp;
int *beg, *end, *mid, target;
printf(" enter the total integers you want to enter (make it less then 20):\n");
scanf("%d", &n);
if (n >= 20) return 0;
printf(" enter the integer array elements:\n" );
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
// sort the loaded array, binary search!
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n-i-1; j++)
{
if (a[j+1] < a[j])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
printf(" the sorted numbers are:");
for(i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
// point to beginning and end of the array
beg = &a[0];
end = &a[n]; // use n = one element past the loaded array!
// mid should point somewhere in the middle of these addresses
mid = beg += n/2;
printf("\n enter the number to be searched:");
scanf("%d",&target);
// binary search, there is an AND in the middle of while()!!!
while((beg <= end) && (*mid != target))
{
// is the target in lower or upper half?
if (target < *mid)
{
end = mid - 1; // new end
n = n/2;
mid = beg += n/2; // new middle
}
else
{
beg = mid + 1; // new beginning
n = n/2;
mid = beg += n/2; // new middle
}
}
// find the target?
if (*mid == target)
{
printf("\n %d found!", target);
}
else
{
printf("\n %d not found!", target);
}
getchar(); // trap enter
getchar(); // wait
return 0;
}
上記のように機能する動的二分探索を実装するために、このプログラムまたは新しいプログラムを変更する方法を誰か提案してください!!