CODEWITHSUNDEEP
javacollectionsbinary-search
Black Swan
Black Swan

Reputation: 851

Why is Collections.binarySearch giving wrong results?

I have created a List where I have kept some strings. But when I am doing binary search within this list, it is returning negative values while the item is in the list.

So far my knowledge positive value will be returned when item in the list. But for some items it is returning negative and for some items positive.

Code:

@Test
public void hello()
{
//  List<String> arlst = new ArrayList<String>();
    List arlst = new ArrayList();
    arlst.add("TP");
    arlst.add("PROVIDES");
    arlst.add("QUALITY");
    arlst.add("TUTORIALS");
    arlst.add("Stop");
    arlst.add("StopP");
    for (Iterator<String> iterator = (Iterator<String>) arlst.iterator();
            iterator.hasNext();)
    {
        Object next = iterator.next();
        System.out.println("next : " + next + " >> Search result : "
            + Collections.binarySearch(arlst, next.toString()));
    }

}

Output:

next : TP >> Search result : -7
next : PROVIDES >> Search result : -1
next : QUALITY >> Search result : 2
next : TUTORIALS >> Search result : -7
next : Stop >> Search result : 4
next : StopP >> Search result : 5

Upvotes: 2

Views: 1685

Answers (3)

Zabuzard
Zabuzard

Reputation: 25903

Reason

You receive strange values since your List is not sorted prior to calling the method, but this is a requirement. Therefore take a look at the methods documentation:

Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Explanation

In order to understand that requirement you need to understand how binary search works. Here is a small illustration:

Binary search illustration

The algorithm takes a look at the element in the middle and compares it to the element to search for. If the given needle is less than the middle element it will continue search to the left, else to the right. It will now take a look at the element to the middle of the reduced range and repeat this process until the element was found or the range can't be divided anymore.

If the elements are not sorted prior, the algorithm will very likely traverse to the wrong direction and obviously not find the element.

Solution

The solution is obvious, sort the List:

Collections.sort(arlst);

Please note that you should not use raw-types. Therefore, write List<String> instead of just List. Then your type-casts will become obsolete too.

In complete the code might then look like

// Setup list
List<String> list = new ArrayList<>();
list.add("TP");
list.add("PROVIDES");
list.add("QUALITY");
list.add("TUTORIALS");
list.add("Stop");
list.add("StopP");

// Sort list
Collections.sort(list);

// Iterate all elements and use binary search
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String element = iter.next();
    System.out.println("element : " + element
        + " >> Search result : "
        + Collections.binarySearch(list, element));
}

Upvotes: 6

zlakad
zlakad

Reputation: 1384

In the API specification:

Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the natural ordering of its elements (as by the sort(List) method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements equal to the specified object, there is no guarantee which one will be found

Upvotes: 0

Anton Tupy
Anton Tupy

Reputation: 969

List must be sorted to use binarySearch on it.

Upvotes: 0

Related Questions