Search code examples
javabinary-search

binarySearch() misidentifying index value

Hopefully a short question, troubleshooting a demo a beginner student brought to my attention.

        int[] nums = {2, 2, 4, 5, 8, 6, 2, 3, 5, 5, 5, 9, 0, 9, 6};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));  //prints sorted array
        System.out.println(Arrays.binarySearch(nums, 6));

//sorted array is: [0, 2, 2, 2, 3, 4, 5, 5, 5, 5, 6, 6, 8, 9, 9]

Code is in a generic main method. It's returning 11 instead of 10, the first instance of the value 6. if I take one of the 6s away it identifies properly as 10. Why?

Thank you.

Short aside, the textbook states that it will return -1 if it doesn't find the value. Instead it returns (-(insertion point) - 1) A little confusing, but the negative tells the important part (not found).

Solution

  • From the Javadoc:

    If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

    That is, depending on the implementation you are using, you might have got 11, you might have got 10.

    If you need to find the first, search backwards from the found element.