java Arrays.binarySearch fails to find target

2019-01-08 01:28发布

问题:

String[] sortedArray = new String[]{"Quality", "Name", "Testing", "Package"};   

// Search for the word "cat" 
int index = Arrays.binarySearch(sortedArray, "Quality");  

I always get -3. Problem is in "Name". Why I can not have "Name" in my array? Any idea?

回答1:

In order to use binarySearch, you will need to sort the array yourself first:

String[] sortedArray = new String[]{"Quality", "Name", "Testing", "Package"};   

java.util.Arrays.sort(sortedArray);

int index = Arrays.binarySearch(sortedArray, "Quality");  


回答2:

The array is must be sorted. From Javadoc of binarySearch():

The range must be sorted into ascending order according to the natural ordering of its elements prior to making this call. If it is not sorted, the results are undefined.



回答3:

An array must be sorted for binary search to work. The javadoc for binarySearch says this:

The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object[]) method) prior to making this call. If it is not sorted, the results are undefined.

(Emphasis added.)

And the reason is simple. The binary search algorithm has a precondition that the input array is sorted.