为何二分查找binsearch的high设为数组边界外？附代码问题排查

一、为什么high要设为&tab[n]而非&tab[n-1] #

K&R这里用的是左闭右开区间的二分查找模型：[low, high)，也就是low指向当前搜索区间的第一个元素，high指向区间末尾的下一个位置，而非最后一个元素。

• 这种设计的好处是：区间内的元素数量可以直接用high - low计算（指针减法，结果是元素个数），逻辑更直观。
• 当你改成high=&tab[n-1]后，区间变成了闭区间[low, high]，但原代码的循环逻辑（low < high）和指针移动规则并没有对应调整，导致搜索范围被错误缩小。比如当目标关键字是数组最后一个元素（比如char或while）时，循环可能提前终止，无法命中。

二、为什么循环用high=mid而非传统的high=mid-1 #

同样是左闭右开区间的特性决定的：

• 当比较后发现目标值小于mid指向的元素时，目标必然在[low, mid)这个左半区间里，所以直接把high设为mid即可，因为high本身就是区间的“开边界”，不包含在搜索范围内。
• 传统闭区间的二分查找才会用high=mid-1，因为闭区间的边界是包含元素的，要排除mid这个已经不符合的元素。你修改成high=mid-1后，相当于在左闭右开的逻辑里错误套用了闭区间的指针移动规则，直接跳过了可能包含目标的区间，导致漏查。

三、程序其他可能的bug排查 #

• 关键字大小写问题：如果输入代码里有大写的Char或WHILE，而keytab里存的是小写关键字，strcmp会匹配失败，导致统计丢失。需要先把读取到的单词转成小写再查找。
• 字符串/注释内的关键字误统计：如果没处理字符串常量（比如"char"）、单行注释（// char）和多行注释（/* while */），这些地方的关键字会被错误统计。需要在读取单词时，先判断当前是否处于字符串或注释状态，跳过这些区域的内容。
• keytab数组的排序和完整性：确保keytab是严格按字典序升序排列的（二分查找的前提），且确实包含了char、while这些关键字。如果数组未正确排序，二分查找会直接失效。
• binsearch的比较逻辑错误：检查strcmp的返回值判断是否写反。比如如果逻辑是“目标小于mid元素时调整high”，但代码里写成了strcmp(word, mid->word) > 0，就会导致搜索方向错误，漏查元素。
• 单词边界判断错误：如果判断“非字符串单词”的逻辑有问题（比如把连字符、下划线开头的标识符当成关键字，或者把关键字的一部分截断），也会导致统计异常。

内容的提问来源于stack exchange，提问作者Zolo_Ryan