Java单链表SinglyLinkedList实现二分查找返回-1问题排查

核心错误点 #

• 右边界初始值错误：链表索引范围是0 ~ size-1，你的代码中right初始化为list.getSize()，会导致访问越界，应该修改为list.getSize() - 1。
• mid节点遍历逻辑错误：要定位到索引为mid的节点，循环次数应为mid次，你当前的循环条件i < mid - 1会少走1步，拿到的永远是mid-1位置的节点，导致元素比对全部错位。
• 二分边界更新逻辑写反：如果中间节点元素大于目标值，说明目标值在左半区间，应该更新right = mid - 1，你当前代码写反为更新left = mid + 1，直接导致查找区间完全偏离，永远找不到目标值。
• 代码冗余：该方法是SinglyLinkedList的实例方法，无需额外传入list参数，直接读取当前实例的size、head属性即可。
• 类型兼容问题：当前仅支持Number类型元素比对，且强制转Integer会导致Long、Double等类型报错，建议改为让泛型E继承Comparable接口实现通用比对，不过此问题不影响你当前的Integer测试用例。

修复后的核心代码 #

public int binarySearchLinkedList(E target) {
    int left = 0;
    // 修复1：右边界初始为size-1
    int right = size - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        Node<E> temp = head;
        // 修复2：循环次数改为mid次，定位到mid索引节点
        for (int i = 0; i < mid; i++) {
            temp = temp.next;
        }

        if (temp.getElement() instanceof Number && target instanceof Number) {
            int tempVal = Integer.parseInt(temp.getElement().toString());
            int targetVal = Integer.parseInt(target.toString());
            if (tempVal == targetVal) {
                return mid;
            } else if (tempVal > targetVal) {
                // 修复3：中间值大于目标值，更新右边界
                right = mid - 1;
            } else {
                // 中间值小于目标值，更新左边界
                left = mid + 1;
            }
        }
    }
    return -1;
}

调用时直接使用list.binarySearchLinkedList(30)即可。

测试结果 #

运行你提供的main方法，查找30会正常返回索引2，符合预期。

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