How to implement dynamic binary search for search and insert operations of n element (C or C++)
- by iecut
The idea is to use multiple arrays, each of length 2^k, to store n elements, according to binary representation of n.Each array is sorted and different arrays are not ordered in any way.
In the above mentioned data structure, SEARCH is carried out by a sequence of binary search on each array.
INSERT is carried out by a sequence of merge of arrays of the same length until an empty array is reached.
More Detail: Lets suppose we have a vertical array of length 2^k and to each node of that array there attached horizontal array of length 2^k.
That is, to the first node of vertical array, a horizontal array of length 2^0=1 is connected,to the second node of vertical array, a horizontal array of length 2^1= 2 is connected and so on. So the insert is first carried out in the first horizontal array, for the second insert the first array becomes empty and second horizontal array is full with 2 elements, for the third insert 1st and 2nd array horiz. array are filled and so on.
I implemented the normal binary search for search and insert as follows:
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;
}
Could anyone please suggest how to modify this program or a new program to implement dynamic binary search that works as explained above!!
