How does Collections.binarySearch work?

Question

I am trying to understand how Collections.binarySearch work in Java. I don't quite understand the output I get.

public static void main(String args[]) {
      // create arraylist       
      ArrayList<String>  arlst=new ArrayList<String> ();


      arlst.add("A");
      arlst.add("D");
      arlst.add("C");
      arlst.add("B");
      arlst.add("E");

      int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

      System.out.println(index);


   }    
}

The output of this code is -1.

And when the elements have been inserted at this order

      arlst.add("D");
      arlst.add("E");
      arlst.add("C");
      arlst.add("B");
      arlst.add("A");

I get 0 as a result. I thought the negative number was a result if the element was not found. Could anybody please clarify the output I receive?

Answer 1

Your data must be sorted according to the given comparator for the binary search to work as intended. (If it's not, the behavior is undefined.)

The list must be sorted into ascending order according to the specified comparator (as by the sort(List, Comparator) method), prior to making this call.

If the data is indeed sorted, the method will return the index of the sought element (if it's found) otherwise (-(insertion point) - 1), as specified in the documentation.

Example:

// Make sure it's sorted
Collections.sort(arlst, Collections.reverseOrder());

int index=Collections.binarySearch(arlst, "D", Collections.reverseOrder());     

System.out.println(index);  // prints 1

Answer 2

■ Searches are performed using the binarySearch() method.
■ Successful searches return the int index of the element being searched.
■ Unsuccessful searches return an int index that represents the insertion point. The insertion point is the place in the collection/array where the element would be inserted to keep the collection/array properly sorted.
        * Return values and 0 indicate successful searches
        * Negative numbers to indicate insertion points
        * The first available insertion point is -1. Therefore,the  actual insertion point is represented as (-(insertion point) -1)

Answer 3

Just to make it clearer - why the output is -1. Yes, you didn't sort it first is a big mistake. But here are some other things to take clear as well.

As @aioobe mentioned in his answer, but he didn't make it clear enough though I think. What does (-(insertion point) - 1) mean? Here is what the doc says.

The index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

So to make the answer more clear: -1 = -0 - 1

What I want to underline here is that the output maybe -2 or -3 or whatever. Because if all elements in the list are less than the specified key, the output will be -list.size() - 1.

Answer 4

Here is the inner workings of the binarySearch method:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package binarysearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class BinarySearch {

    static ArrayList<String> strings;
    public static void main(String[] args) {
        String sample = "a quick brown fox jumped right over the lazy dog while an active lion was nowhere in sight";
        String[] simpleArray = sample.split(" ");
        strings = new ArrayList(Arrays.asList(simpleArray));
        Collections.sort(strings);
        // Enter a search string; here it is "lazy"
        binarySearch(strings, "lazy");
        System.out.println("");
        // Print the Array contents for convenience
        printArrayList(strings);
    }
    
    static void printArrayList(ArrayList<String> strings) {
        int i = 0;
        for (String s: strings) {
            i++;
            System.out.println(i + s );
        }
    }
    
    
    
    static void binarySearch (ArrayList<String> strings, String searchString) {
        boolean debug = true;
        int low = 0;
        int high = strings.size();
        int mid = 0;
        while (low <= high) {
            // The > symbol marks the hits before search is concluded
            System.out.print(">");
            mid = (high + low) / 2;
            
            int comparison = strings.get(mid).compareToIgnoreCase(searchString);
            if (comparison > 0) {
                high = mid - 1;
            } else if (comparison < 0) {
                low = mid + 1;
            } else {
                int temp = mid;
                System.out.println("Found '" + searchString + "' at: " + (temp + 1) );
                break;
            }
        }
    }
    
}