Skip to content
Advertisement

Couldn’t implement binary search on linked list

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)

JavaScript

All class for better understanding;

JavaScript

And the main method;

JavaScript

It returns;

JavaScript

Advertisement

Answer

I’m guessing this line is the biggest issue:

JavaScript

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.
User contributions licensed under: CC BY-SA
5 People found this is helpful
Advertisement