无法在链表上实现二进制搜索

Question

我是一名修读数据结构课程的 cse 学生。尝试对我的 SinglyLinkedList class 实施二进制搜索算法，但我失败了。你能检查一下有什么问题吗？

相关方法；我已经调试过了，它只是在这边进入循环：else if(temp.getElement() > target)

    public int binarySearchLinkedList(SinglyLinkedList<E> list, E target) {
    int left = 0;
    int right = list.getSize();

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

        Node<E> temp = head;
        for (int i = 0; i < mid - 1; i++) {
            temp = temp.next;
        }

        if (temp.getElement() instanceof Number && target instanceof Number) {
            if (Integer.parseInt(temp.getElement().toString()) == Integer.parseInt(target.toString())) {
                return mid;
            } else if (Integer.parseInt(temp.getElement().toString()) > Integer.parseInt(target.toString())) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

所有 class 为了更好地理解；

public class SinglyLinkedList<E> {

private static class Node<E> {
    private E element;
    private Node<E> next;

    public Node(E e, Node<E> n) {
        element = e;
        next = n;
    }

    private E getElement() {
        return element;
    }

    private Node<E> getNext() {
        return next;
    }

    private void setNext(Node<E> n) {
        next = n;
    }
}

private Node<E> head;
private Node<E> tail;
private int size;

public SinglyLinkedList() {
};

public int getSize() {
    return size;
}

public void append(E e) {
    if (head == null) {
        head = new Node<E>(e, null);
        tail = head;
        size++;
        return;
    }

    Node<E> temp = head;
    while (temp != tail) {
        temp = temp.next;
    }
    temp.setNext(tail = new Node<E>(e, null));
    size++;
    return;
}

public int binarySearchLinkedList(SinglyLinkedList<E> list, E target) {
    int left = 0;
    int right = list.getSize();

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

        Node<E> temp = head;
        for (int i = 0; i < mid - 1; i++) {
            temp = temp.next;
        }

        if (temp.getElement() instanceof Number && target instanceof Number) {
            if (Integer.parseInt(temp.getElement().toString()) == Integer.parseInt(target.toString())) {
                return mid;
            } else if (Integer.parseInt(temp.getElement().toString()) > Integer.parseInt(target.toString())) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;

}

public String toString() {
    StringBuilder sb = new StringBuilder();

    Node<E> temp = head;
    while (temp != tail) {
        sb.append(temp.getElement()).append(", ");
        temp = temp.next;
        if (temp == tail) {
            sb.append(temp.getElement());
        }
    }
    return sb.toString();
}

}

和主要方法；

public static void main(String[] args) {
    SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
    list.append(10);
    list.append(20);
    list.append(30);
    list.append(40);
    list.append(50);
    list.append(60);
    list.append(70);
    list.append(80);
    list.append(90);
    list.append(100);
    System.out.println(list);
    System.out.println(list.binarySearchLinkedList(list, 30));
}

它returns;

10, 20, 30, 40, 50, 60, 70, 80, 90, 100
-1

Answer 1

我猜这行是最大的问题：

    for (int i = 0; i < mid - 1; i++) {

考虑如果 mid 为 1 会发生什么。循环不会执行，因为 0 < 1-1 不是这种情况。所以被检查的节点不会是你认为的那个。永远不会检查索引 mid 处的实际节点。所以外循环最终会退出，永远不会找到目标。大概你的方法以 return -1;.

结尾

其他问题包括：

您正在将 right 初始化为一个独占值，但在其他地方将其视为包含性值。考虑使用 int right = list.getSize() - 1;
您声明了一个泛型方法，但仅为 Integer 实现了它。解决此问题的一种方法是将通用类型限制为支持 Comparable 的类型 - 例如 E extends Comparable<E>.
您正在链表中实现二进制搜索。在链表中，线性搜索会更简单且效率不低。或者您可以使用支持按索引进行恒定时间访问的数据结构，例如数组或 ArrayList。

无法在链表上实现二进制搜索

Couldn't implement binary search on linked list

java

linked-list

binary-search

data-structures