如何实现n元素的搜索和插入操作的动态二进制搜索
根据n的二进制表示，我们的想法是使用多个长度为2 ^ k的数组来存储n个元素。每个数组都被排序，不同的数组不以任何方式排序。
在上述数据结构中，SEARCH通过每个arrays上的二进制搜索序列来执行。 INSERT由相同长度的数组的合并序列执行，直到到达空数组。
更多细节：假设我们有一个长度为2 ^ k的垂直数组，并且该数组的每个节点都附加了长度为2 ^ k的水平数组。
也就是说，对于垂直arrays的第一节点，连接长度为2 ^ 0 = 1的水平arrays，对于垂直arrays的第二节点，连接长度为2 ^ 1 = 2的水平arrays，依此类推。 因此，首先在第一水平arrays中执行插入，对于第二插入，第一arrays变为空并且第二水平arrays充满2个元素，对于第三插入第一和第二arrays水平。 数组被填充等等。 我实现了搜索的常规二进制搜索并插入如下：
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 < ni-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_value和row_high_value 。
找到确切的行后，是时候...
行二进制搜索
应用于该行的二进制搜索是增强二进制搜索。 增强是确定行的第一列和最后一列的数组索引。 可以使用等式1计算这些列索引。
细节留给读者练习。
（顺便说一句，制作图片和图表在遇到问题时总是一个有用的做法，无论是计算机算法还是物理问题。）
维护数据结构
通过将其作为单个arrays处理，可以最简单地执行此数据结构的维护，插入和删除元素。 找到插入索引后， 向下移动元素以为另一个元素腾出空间，然后插入新元素。
更好的数据结构
更好的数据结构可能是具有[value, pointer, length]元素的数组。 指针指向另一个数组。 length字段表示数组的长度。 这允许在值字段上使用标准二进制搜索。 可以使用指针和长度字段将标准二进制搜索应用于行数组。 方便的是C和C ++语言带有标准的二进制搜索function， 已经过测试，您不必浪费时间重写 。
动态二进制搜索确实是一个很酷的算法。 它的参考是算法导论（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<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