javacollectionsbinary-searchlower-boundupperbound

Is Collections.binarySearch(list,key)*-2 is lower_bound for key when key not found in java List?

Consider the following code .

  List<Integer> list = new Random().ints(10,1,50).boxed().collect(Collectors.toList());
        list.sort(Comparator.naturalOrder());
        System.out.println(list);
        System.out.print("Enter key :");
        Scanner sc = new Scanner(System.in);
        int key = sc.nextInt();
        int ans = Collections.binarySearch(list, key);

        String result = String.format("ans = %d, list.at(ans*-1) = %d , lower bond = %d , upper bound = %d ", ans,list.get(ans*-1),list.get(ans*-1 -2 ) , 
                list.get(ans * -1 -1));
        System.out.println(result);

I was working on binarySearch method given by Collections class. When key does not present in list, it gives these weird numbers in negative. I mapped them to their lower bound and upper bound. I worked on several examples and always got it right.

see this

screenshot

For every input I have given it return correct upper bound and lower bound inside the list. Can Anyone explain to me ? Whats happening inside the hood ?

Solution

  • This is the correct and documented behavior of the Collections.binarySearch. From the JavaDoc:

    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.

    Note the last sentence (emphasized by myself), that there is guaranteed the return value is 0 or positive if the key is found. This implies that a negative value is returned if the required element is not present in the input List.

    Edit: The negative value is actually not that unpredictable as it looks like. Browsing the source code of java.util.Collections and its private methods calculating the result ...

    ... both of them return the following in case the key was not found:

    return -(low + 1);  // key not found

    Therefore the returned value is the negative index of where the searched element was expected to be located at.