Couldn't implement binary search on linked list

Question

i am a cse student who takes data structures course. Trying to implement binary search algorithm to my SinglyLinkedList class, somehow i've failed. Could you check it what's wrong please ?

The related method; I've debugged and it just enters the loops this side: 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;
            }
        }
    }

All class for better understanding;

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();
}

}

And the main method;

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));
}

It returns;

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

Answer 1

I'm guessing this line is the biggest issue:

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

Consider what happens if mid is 1. The loop won't execute, because it is not the case that 0 < 1-1. So the inspected node won't be the one you think it is. The actual node at index mid will never be inspected. So the outer loop will eventually exit, never having found the target. Presumably your method ends with return -1;.

Other issues include:

• You're initializing right to an exclusive value, but treat it as inclusive elsewhere. Consider using int right = list.getSize() - 1;
• You've declared a generic method, but implemented it only for Integer. One way around this would be to limit the generic type to one that supports Comparable - e.g., E extends Comparable<E>.
• You're implementing a binary search in a linked list. In a linked list, linear search would be simpler and no less efficient. Or you could use a data structure that supports constant-time access by index, such as an array or ArrayList.