比较来自 K&R 的两个二进制搜索(数组索引与指针)

Question

我的问题在代码下面。

结构一章中描述了 K&R 中的两种不同的 bin 搜索，一种使用数组索引来处理结构(第 134 页)，另一种使用指向结构的指针(第 136 页)。

binsearch 决定结构中的特定字符串 keytab[n].word 是否与数组中的字符串 word 匹配。

这是结构声明本身及其初始化。该结构包含一堆 c 键盘和它们出现的次数。

    struct key {
       char *word;
       int count;
   } keytab[] = {
       "auto", 0,
       "break", 0,
       "case", 0,
       "char", 0,
       "const", 0,
       "continue", 0,
       "default", 0,
       /* ... */
       "unsigned", 0,
       "void", 0,
       "volatile", 0,
       "while", 0
   };

这是第一个binsearch

/* binsearch:  find word in tab[0]...tab[n-1] */
   int binsearch(char *word, struct key tab[], int n)
   {
       int cond;
       int low, high, mid;

       low = 0;
       high = n - 1;
       while (low <= high) {
           mid = (low+high) / 2;
           if ((cond = strcmp(word, tab[mid].word)) < 0)
               high = mid - 1;
           else if (cond > 0)
               low = mid + 1;
           else
               return mid;
       }
       return -1;
   }

这是使用指向结构的指针而不是数组索引的 binsearch:

/* binsearch: find word in tab[0]...tab[n-1] */
   struct key *binsearch(char *word, struct key *tab, int n)
   {
       int cond;
       struct key *low = &tab[0];
       struct key *high = &tab[n];
       struct key *mid;

       while (low < high) {
           mid = low + (high-low) / 2;
           if ((cond = strcmp(word, mid->word)) < 0)
               high = mid;
           else if (cond > 0)
               low = mid + 1;
           else
               return mid;
       }
       return NULL;
   }

有两点我不明白。

首先，我们假设 n 是两种情况下结构数组的大小。

在第一个binsearch中，n-1被描述为搜索的上限。匹配字符串实际上可以出现在tab[high = n-1].word中，但不会出现在tab[n].word中。

在第二个 binsearch 中，上限被写成 struct key *high = &tab[n]，就好像字符串可以在那里出现一样，即使“解引用它是非法的”(第 138 页，上)。它应该是一个 NULL 指针。

为什么不写成struct key *high = &tab[n-1]？数组这样的东西似乎总是让我在 c 中感到困惑。

第二个我不明白的是

高 = 中;

在第二个 binsearch 中相对于

high = mid -1;

在第二个 binsearch 中。

为什么第二个不是high = mid-1？

Answer 1

第一个问题的答案是，通过指针减法，您将得到减去偏移量的结果，即如果 low = &tab[0] 和 high = &tab[n- 1]，high - low的结果是n-1，而不是n。要获得中点你需要 n 虽然 (n/2)，所以 high 应该等于 &tab[n]。第二个问题的答案是 mid 总是比你感兴趣的元素高 1(因为我们知道它已经不是答案，而且它上面的所有元素都不是)，所以现在是 1您感兴趣的数组部分。因此，第一个问题的逻辑适用，我们将高点留在数组“末尾”之后的位置。