How to implement dynamic binary search for search and insert operations of n element

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}; 
    开发者_JS百科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!!

Smells like homework because there are generally better methods to implement the design.

Let me clarify the requirement: Given an array of contiguous integers, they can be perceived to be in the following order:

row 0: array[0] #
row 1: array[1] # #
row 2: array[3] # # # #
row 3: array[7] # # # # # # # #

The search algorithm, according to my understanding, is:

1. Outer binary search

Apply a binary search to the first "column". The result will find the row to search.

2. Row binary search

Apply a binary search to the row to find the exact value.

The Outer Binary Search

The next step is to modify an existing binary search algorithm to advance the "lowest" and "highest" indices according to the array layout.

Looking at the layout above, there appears to be a pattern with the array indices for each row. Looks like:

  [Equation 1] index = power(2, row #) - 1

In a binary search, each iteration picks a midpoint, which is half way between the highest point and the lowest point, normally calculated as:

[Equation 2} midpoint = ((highest - lowest) / 2) + lowest

To make the understanding easier, let us adopt two indexing conventions: row index and column index. The row index is the row number, according to the layout. The column index will be the position within the row. The layout above contains 4 rows. Row 2 has 4 columns.

So to find the row, we use the midpoint formula:

   row_midpoint = ((row_highest + row_lowest) / 2) + row_lowest

Before a value can be compared it must be located first. The location is obtained by plugging the row_midpoint value into Equation 1.

array_midpoint_index = (1 << row_midpoint) - 1

The value is then obtained by using this array_midpoint_index: value = array[array_midpoint_index]

To avoid repeating calculations, I recommend saving the values, such as row_low_value and row_high_value as examples.

After the exact row is found it is time for the ...

Row Binary Search

The binary search applied to the row is an augmented binary search. The augmentation is determining the array indices of the first and last columns of the row. These column indices can be computed using Equation 1.

Details are left as an exercise for the reader.
(BTW, making pictures and diagrams is always a helpful practice when getting stuck on a problem, whether it be computer algorithms or physic's word problems.)

Maintaining the Data Structure

Maintenance of this data structure, inserting and removing elements, is easiest performed by treating it as a single array. Once the insertion index is found, move elements down to make room for another, then insert the new element.

A Better Data Structure

A better data structure may be to have an array of [value, pointer, length] elements. The pointer would point to another array. The length field indicates the length of the array. This allows for using a standard binary search on the value field. A standard binary search can be applied to the row array by using the pointer and length fields. The convenience is that the C and C++ languages come with standard binary search functions, already tested that you don't have to waste time rewriting.

Dynamic binary search really is a cool algorithm. The reference for it is Introduction to Algorithms (Cormen, Leiserson and Rivest) problem 18-2 and it is closely related to the online mergesort (Knuth TAOCP ex 5.2.4-17). It has O(log(n)) average successful search time. Worst case succesful and unsuccesful search are both O(log²(n)). And is much easier to code than balanced search trees.

The search is fairly straight forward, you just have to search each row until you find something (start at the biggest). I've implemented an insertion below. The merge routine does all the sorting. Note that each row is an int * which is the same as an array of ints (or NULL). If I was making a high performance version, I'd look into caching some smaller sized arrays as malloc and free tend to be slow.

int *row[30];
int lastrow=0;
void dbs_insert(int v);
int *dbs_merge(int *a, int *b, int len);

void dbs_insert(int v) {
    int *new_row;
    int i;
    new_row=malloc(sizeof(int));
    new_row[0]=v;
    i=0;
    while (row[i]!=NULL) {
        new_row=dbs_merge(row[i],new_row,1<<i);
        row[i]=NULL;
        i++;
    }
    row[i]=new_row;
    if (i>lastrow) lastrow=i;
}

int *dbs_merge(int *a, int *b, int len) {
    int ai=0;
    int bi=0;
    int ci=0;
    int *c;
    c=malloc((2*len)*sizeof(int));
    while (ai <len && bi < len) {
        if (a[ai]<=b[bi]) {
            c[ci++]=a[ai++];
        } else {
            c[ci++]=b[bi++];
        }
    }
    while (ai<len)
        c[ci++]=a[ai++];
    while (bi<len)
        c[ci++]=b[bi++];
    free(a);
    free(b);
    return c;
}