符号表两边界键间严格计数（排除边界、支持无序边界）实现问题

功能需求说明 #

• 统计目标：严格计算两个边界键之间包含的键总数量
• 规则约束：
  • 计数结果必须排除两个边界键本身，不将其纳入统计范围
  • 传入的两个边界键无需预先排序，方法内部可自动识别上下界完成统计

现有实现代码 #

public int countRangeStrict(Key key1, Key key2) {
    if (key1.compareTo(key2) == 0) return 0;
    if (contains(key2)) return rank(key2) - rank(key1) + 1;
    else return (rank(key2) - rank(key1));
}

public int rank(Key key) {
    if (key == null) throw new IllegalArgumentException();
    int lo = 0;
    int hi = N - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int temp = key.compareTo(this.key[mid]);
        if (temp < 0) hi = mid - 1;
        else if (temp > 0) lo = mid + 1;
        else return mid;
    }
    return lo;
}

测试运行结果 #

测试使用的基础键集合为有序存储的BEIOU，各用例执行情况如下：

• 传入key1为A、key2为Z，实际返回5，与预期一致，测试通过
• 传入key1为Z、key2为A，实际返回-5，与预期返回5不符，测试失败
• 传入key1为J、key2为N，实际返回0，与预期一致，测试通过
• 传入key1为C、key2为O，实际返回3，与预期返回2不符，测试失败
• 传入key1为B、key2为P，实际返回4，与预期返回3不符，测试失败

已定位的核心缺陷 #

• 方法硬编码默认将第一个传入参数key1作为区间下界、第二个参数key2作为区间上界，完全没有处理参数传入顺序颠倒的场景，会直接返回负数的错误结果
• 计数逻辑没有匹配“排除边界键本身”的规则，当边界键存在于符号表中时，计算得到的结果会错误将边界键纳入计数，导致返回值比预期大1

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