CODEWITHSUNDEEP
javabinary-search
Owl
Owl

Reputation: 9

String binary search in Java

I am learning using binary search in Java. In an integer list it returns expected index but in char or a String list (code example) it returns a negative index, which is not expected (index = -4).

List<String> str = new ArrayList<>();
str.add("Hey");
str.add("Hi");
str.add("Bye");
int index = Collections.binarySearch(str,"Hi");
System.out.println(index);

Upvotes: 0

Views: 619

Answers (2)

GhostCat
GhostCat

Reputation: 140427

The pre-condition of a binary search is: the underlying data must be sorted.

So, sort that list first.

And then you want to check that the index returned by that method is between 0 and the size() of your list. It is a bit naive to expect that any string could be found in your list and return a non-zero index.

Beyond that; the real answer here: don't just blindly use a built-in functionality. Read its javadoc first to understand what this method is doing, and for example: what values it will return to you!

Upvotes: 3

Eran
Eran

Reputation: 393781

Your List must be sorted in order for binary search to work. The natural ordering of Strings is lexicographical order, so "Bye" should come before "Hey" and "Hi".

Try 

List<String> str = new ArrayList<>();
str.add("Bye");
str.add("Hey");
str.add("Hi");

int index = Collections.binarySearch(str,"Hi");
System.out.println(index);

Upvotes: 2

Related Questions