基于有序单链表的二分查找Java实现问题求助

错误点分析与修复方案 #

1. 内部类实例化错误 #

Node作为Main的非静态内部类，静态方法中无法直接创建实例。将Node改为静态内部类，同时把LinkedList也设为静态内部类，避免外部类实例依赖，确保静态方法能正常调用。

2. 链表顺序与查找逻辑不匹配 #

原push方法是头插法，插入后链表为降序，但二分查找逻辑是按升序设计的（当mid.data > value时，目标值应在右半部分）。改为尾插法保证链表始终升序，让查找逻辑与链表顺序匹配。

3. 方法返回值不符合要求 #

题目要求binarySearch返回boolean类型，原代码返回Node，修改方法返回值：找到目标值返回true，否则返回false。

4. 元素数量与用户输入处理 #

原main方法仅插入6个元素，补充至10个以上；添加Scanner处理用户输入的目标值，实现交互查询功能。

5. 循环条件修正 #

原do-while循环条件last == null || last != start逻辑错误，可能导致死循环，调整为start != last，并在循环结束后额外检查start节点，确保边界情况被覆盖。

修正后的完整代码 #

import java.util.Scanner;

public class Main {
    // 静态内部类Node，避免外部类实例依赖
    static class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
    }

    // 静态内部类LinkedList，包含插入和二分查找方法
    static class LinkedList {
        // 尾插法，保证链表升序
        static Node append(Node head, int data) {
            Node newNode = new Node(data);
            if (head == null) {
                return newNode;
            }
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            return head;
        }

        // 找到start到last之间的中间节点
        static Node middleNode(Node start, Node last) {
            if (start == null) {
                return null;
            }
            Node slow = start;
            Node fast = start.next;

            while (fast != last && fast != null) {
                fast = fast.next;
                if (fast != last && fast != null) {
                    slow = slow.next;
                    fast = fast.next;
                }
            }
            return slow;
        }

        // 返回boolean类型的二分查找方法
        static boolean binarySearch(Node head, int value) {
            Node start = head;
            Node last = null;

            do {
                Node mid = middleNode(start, last);
                if (mid == null) {
                    return false;
                }
                if (mid.data == value) {
                    return true;
                } else if (mid.data < value) {
                    // 目标值在右半部分，调整start
                    start = mid.next;
                } else {
                    // 目标值在左半部分，调整last
                    last = mid;
                }
            } while (start != last);

            // 最后检查start节点
            return start != null && start.data == value;
        }

        public static void main(String[] args) {
            Node head = null;
            // 插入至少10个有序整数
            head = append(head, 2);
            head = append(head, 5);
            head = append(head, 7);
            head = append(head, 11);
            head = append(head, 15);
            head = append(head, 18);
            head = append(head, 22);
            head = append(head, 25);
            head = append(head, 30);
            head = append(head, 33);

            // 处理用户输入
            Scanner scanner = new Scanner(System.in);
            System.out.print("请输入要查找的目标值：");
            int target = scanner.nextInt();

            // 执行查找并输出结果
            if (binarySearch(head, target)) {
                System.out.println("元素 " + target + " 已找到");
            } else {
                System.out.println("元素 " + target + " 未找到");
            }
            scanner.close();
        }
    }
}

代码说明 #

• 尾插法append：确保每次插入的元素都在链表尾部，维持升序排列。
• middleNode方法：快慢指针法找到中间节点，避免遍历整个链表统计长度，符合二分查找的效率要求。
• binarySearch方法：调整边界逻辑，确保每次缩小查找范围，最终返回boolean结果。
• 用户输入处理：使用Scanner获取用户输入的目标值，实现交互查询。
• 元素数量：插入了10个有序整数，满足题目要求。

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