2

这个想法是使用多个数组，每个数组长度为 2^k，根据 n 的二进制表示来存储 n 个元素。每个数组都是排序的，不同的数组不以任何方式排序。

在上述数据结构中，SEARCH 是通过对每个数组进行一系列二分查找来执行的。INSERT 通过一系列相同长度的数组合并执行，直到到达一个空数组。

更多细节：假设我们有一个长度为 2^k 的垂直数组，并且该数组的每个节点都附有长度为 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;
  }

谁能建议如何修改这个程序或一个新程序来实现如上所述的动态二进制搜索！

4

2 回答 2

1

闻起来像作业，因为通常有更好的方法来实现设计。

让我澄清一下要求：给定一个连续整数数组，它们可以被认为是以下顺序：

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_value和row_high_value作为示例。

找到确切的行后，就该...

行二分搜索

应用于行的二进制搜索是增强的二进制搜索。扩充是确定行的第一列和最后一列的数组索引。这些列索引可以使用公式 1 计算。

细节留给读者练习。
（顺便说一句，当遇到问题时，无论是计算机算法还是物理单词问题，制作图片和图表总是一种有用的做法。）

维护数据结构

这种数据结构的维护，插入和删除元素，最容易通过将其视为单个数组来执行。找到插入索引后，向下移动元素为另一个元素腾出空间，然后插入新元素。

更好的数据结构

更好的数据结构可能是有一个[value, pointer, length]元素数组。指针将指向另一个数组。长度字段表示数组的长度。这允许在值字段上使用标准的二进制搜索。通过使用指针和长度字段，可以将标准二进制搜索应用于行数组。方便之处在于 C 和 C++ 语言带有标准的二进制搜索功能，已经过测试，您不必浪费时间重写。

于 2010-04-08T19:30:56.150 回答
1

动态二分搜索确实是一个很酷的算法。它的参考是算法介绍（Cormen，Leiserson 和 Rivest）问题 18-2，它与在线合并排序（Knuth TAOCP ex 5.2.4-17）密切相关。它的平均成功搜索时间为 O(log(n))。最坏情况成功和不成功的搜索都是 O(log 2 (n))。并且比平衡搜索树更容易编码。

搜索相当简单，您只需搜索每一行，直到找到一些东西（从最大开始）。我在下面实现了一个插入。合并例程进行所有排序。请注意，每一行都是一个 int *，它与 int 数组（或 NULL）相同。如果我正在制作高性能版本，我会考虑缓存一些较小的数组，因为 malloc 和 free 往往很慢。


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;
}
于 2010-06-07T00:35:30.263 回答