我想使用链表进行二分查找

Question

搜索技巧 使用适当的变量名称并遵守编码标准。 清晰地处理用户输入并显示输出。 在二分搜索方法中使用迭代/递归二分搜索 提交包含您的实现的 Java 文件 (StudentName_BinaryLinkedList.java)。将学生姓名替换为您的姓名

位置1的问题 1

10分

位置1的问题 给定一个已排序的整数单链表，并且要求您实现二分搜索算法以在链表中查找目标值。编写一个包含以下内容的 Java 程序：

定义一个名为Node的类来表示链表中的一个节点。该类应该有一个整数值和对下一个节点的引用。

定义一个名为Linked List的类来表示链表。该类应该具有插入节点的方法和名为“Binary Search”的方法，该方法将目标值作为参数，如果目标值存在于链表中，则返回 true，否则返回 false。实现链表的二分查找算法。

在main方法中，创建Linked List类的实例，并向链表中插入至少10个已排序的整数。提示用户输入要在链表中搜索的目标值。调用二分查找方法判断目标值是否存在并显示结果。

这是我尝试过的，但我得到了同样的错误

https://replit.com/@JordanBrown24/CS114#Main.java

public class Main
{ 
  class Node
  {
      int data;
      Node next;
      Node(int d)
      {
          data = d;
          next = null;
      }
  }

  class LinkedList
    
  {
      static Node push(Node head, int data)
      {
          Node newNode = new Node(data);
          newNode.next = head;
          head = newNode;
          return head;
      }
      static Node middleNode(Node start, Node last)
      {
          if (start == null)
              return null;

          Node slow = start;
          Node fast = start.next;

          while (fast != last)
          {
              fast = fast.next;
              if (fast != last)
              {
                  slow = slow.next;
                  fast = fast.next;
              }
          }
          return slow;
      }
      static Node binarySearch(Node head, int value)
      {
          Node start = head;
          Node last = null;

          do
          {

              Node mid = middleNode(start, last);
              if (mid == null)
                  return null;
              if (mid.data == value)
                  return mid;
              else if (mid.data > value)
              {
                  start = mid.next;
              }
              else
                  last = mid;
          } while (last == null || last != start);

          return null;
      }
      public static void main(String[] args)
      {
          Node head = null;

          head = push(head, 2);
          head = push(head, 5);
          head = push(head, 7);
          head = push(head, 11);
          head = push(head, 15);
          head = push(head, 18);
          int value = 7;

          if (binarySearch(head, value) == null)
          {
              System.out.println("Element not found");
          }
          else
          {
              System.out.println("Element found");
          }
      }
  }
}  

Answer 1

一些问题：

• 您正在尝试从静态上下文访问

  Node

  ，但

  Node

  不是静态

• 由于您没有创建

  Main

  实例，

  Node

  和

  LinkedList

  类应定义为静态（除非您将它们创建为顶级类）。

• 您应该定义instance方法。例如，将

  push

  定义为需要提供头节点作为参数的静态方法并不是最佳实践。相反

  push

  应该是一个实例方法。

• head

  应该是

  LinkedList

  类的实例字段，而不是

  main

  中的变量。

• main函数应该创建一个

  LinkedList

  实例。

这是您的代码，考虑了这些备注：

public class Main
{ 
    static class Node // Mark as static, since we don't create a Main instance
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    static class LinkedList  // Mark as static
    {
        Node head = null; // Should be a field, not a function argument
      
        Node push(int data) // Should not be static
        {
            Node newNode = new Node(data);
            newNode.next = head;
            head = newNode;
            return head;
        }
      
        static Node middleNode(Node start, Node last)
        {
            if (start == null || start == last) // Also capture case of 1 node
                return start;

            Node slow = start;
            Node fast = start.next;

            while (fast != last)
            {
                fast = fast.next;
                if (fast != last)
                {
                    slow = slow.next;
                    fast = fast.next;
                }
            }
            return slow;
        }
      
        Node binarySearch(int value)  // Should not be static
        {
            Node start = head;
            Node last = null;

            do
            {
                Node mid = middleNode(start, last);
                if (mid == null)
                    return null;
               if (mid.data == value)
                    return mid;
                else if (mid.data > value)
                    start = mid.next;
                else
                    last = mid;
            } while (last != start); // Don't need to test last is null
            return null;
        }
    }
  
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList(); // Should create instance
        list.push(2);  // Use the instance to push data
        list.push(5);
        list.push(7);
        list.push(11);
        list.push(15);
        list.push(18);
        int value = 18;

        if (list.binarySearch(value) == null)
        {
            System.out.println("Element not found");
        }
        else
        {
            System.out.println("Element found");
        }
    }
} 

最后一点，这个代码挑战并没有教导正确的事情：二分搜索在链表世界中没有地位。那里效率不高。在搜索链表时，线性搜索更有意义，并且通常会比二分搜索更快地找到节点。