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

Question

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!!

Answer 1

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.