一千萬個為什麽

搜索

如何實現n元素的搜索和插入操作的動態二進制搜索

根據n的二進制表示,我們的想法是使用多個長度為2 ^ k的數組來存儲n個元素。每個數組都被排序,不同的數組不以任何方式排序。

在上述數據結構中,SEARCH通過每個陣列上的二進制搜索序列來執行。 INSERT由相同長度的數組的合並序列執行,直到到達空數組。

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.

也就是說,對於垂直陣列的第一節點,連接長度為2 ^ 0 = 1的水平陣列,對於垂直陣列的第二節點,連接長度為2 ^ 1 = 2的水平陣列,依此類推。因此,首先在第一水平陣列中執行插入,對於第二插入,第一陣列變為空並且第二水平陣列充滿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;
  }

任何人都可以建議如何修改此程序或新程序,以實現如上所述的動態二進制搜索!

最佳答案

聞起來像家庭作業,因為通常有更好的方法來實現設計。

讓我澄清一下要求: 給定一組連續的整數,可以認為它們按以下順序排列:

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

根據我的理解,搜索算法是:

1。外部二進制搜索

將二進制搜索應用於第一個“列”。 結果將找到要搜索的行。

2。行二進制搜索

將二進制搜索應用於該行以查找確切的值。

外部二進制搜索

下一步是修改現有的二進制搜索算法,以根據數組布局推進“最低”和“最高”索引。

查看上面的布局,似乎每個行都有一個帶有數組索引的模式。好像:

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

在二分搜索中,每次叠代選擇一個中點,該中點位於最高點和最低點之間,通常計算如下:

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

為了使理解更容易,讓我們采用兩種索引約定:行索引列索引。根據布局,行索引是行號。 列索引將是行內的位置。上面的布局包含4行。第2行有4列。

所以要找到行,我們使用中點公式:

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

在可以比較值之前,必須先將其定位。通過將 row_midpoint 值插入等式1來獲得該位置。

array_midpoint_index = (1 << row_midpoint) - 1

然後使用此 array_midpoint_index 獲取該值:     value = array [array_midpoint_index]

為避免重復計算,建議您保存值,例如 row_low_valuerow_high_value

找到確切的行後,是時候...

行二進制搜索

應用於該行的二進制搜索是增強二進制搜索。增強是確定行的第一列和最後一列的數組索引。可以使用等式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.)

維護數據結構

通過將其作為單個陣列處理,可以最簡單地執行此數據結構的維護,插入和刪除元素。找到插入索引後,將元素向下移動為另一個元素騰出空間,然後插入新元素。

更好的數據結構

更好的數據結構可能是一個 [value,pointer,length] 元素的數組。指針指向另一個數組。 length 字段表示數組的長度。這允許在值字段上使用標準二進制搜索。通過使用指針length 字段,可以將標準二進制搜索應用於數組。方便的是C和C ++語言帶有標準的二進制搜索功能,已經過測試,你不必浪費時間重寫

轉載註明原文: 如何實現n元素的搜索和插入操作的動態二進制搜索