CODEWITHSUNDEEP
javacollections
Sunny
Sunny

Reputation: 2144

why getting wrong answer when using Collections.binarySearch()

public class BinarySearchCollections {
  public static void search(List<String> list) {
    list.clear();
    list.add("b");
    list.add("a");
    list.add("c");
    System.out.println(Collections.binarySearch(list, "b"));
    System.out.println(list);
  }
  public static void main(String[] args) {
    List<String> lis = new ArrayList<String>();
    BinarySearchCollections bs = new BinarySearchCollections();
    bs.search(lis);
  }
}

Here I am getting ans as -3 (as it is telling me at what location it is going to be added) but I already have b in my list.

Upvotes: 0

Views: 517

Answers (2)

Cemafor
Cemafor

Reputation: 1653

Collections.binarySearch() does not ensure the list is sorted before attempting to search. You need to make sure that is the case before calling binarySearch().

If it did check the list first, it would turn a O(lg(n)) search into O(n+lg(n)) check/search, degrading performance. (O(nlg(n)) if it had to sort the list as well).

You should probably check out the List.Sort() method.

Upvotes: 1

dlev
dlev

Reputation: 48596

Your original list isn't sorted, so binary search is going to give you a nonsense answer.

Imagine the steps it actually takes:

"Is b > a? Yes, so look higher."

"Is b > c? No, but we can't go lower, so insert at index 2 (aka return -3.)"

If you want binary search to work, give it a list on which it can take meaningful steps, and then give you the correct answer.

Upvotes: 1

Related Questions