Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

binarySearch() method of Arrays

Astha Sharma
Ranch Hand

Joined: Oct 15, 2011
Posts: 244

gives the output-

four one three two
1
two three one four
2

At line1, we have a sorted array of strings 'sa'. Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument? Why the 'two argument' version of this method doesn't work here and gives unpredictable output?

Astha - OCPJP 6 (90%)
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1363

Hi Astha Sharma,

I assume you've understood all 4 lines of output. If yes, then the questions are quite straightforward.
Astha Sharma wrote:Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?

This is because, at line no. 16 of your snippet, you've sorted the array as per your own comparator (which sorts array in reverse order). Now, when you perform a binary search, the default logic (i.e. 2 arg method) assumes that array is sorted by default order (e.g. alphabetically in case of String etc.) and will try to search the array, but as we know that the array is not sorted as per default ordering, but as per ReverseSort ordering.
So, there should be a way to tell binary search algorithm that by what logic the array is sorted, then only it will be able to search the array properly. Otherwise, it would assume that array is sorted with default logic, and will give 'unpredictable result'.

I hope this helps.

Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Zeeshan Sheikh
Ranch Hand

Joined: Nov 20, 2011
Posts: 144

At line1, we have a sorted array of strings 'sa'.

//line 1: Searches the specified array (sa) for the specified object (rs) using the binary search algorithm.

Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?

Its the logic whoever wrote the program !! The following method is used

//line 2: Method Signature: public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
The array to be searched is sa
key the value to be searched for is one
c the comparator by which array is ordered (rs). (which is why comparator argument is used)

CompareTo comparison is based on the Unicode value of each character in the strings.

The result is a negative integer if this String object lexicographically precedes the argument string.
The result is a positive integer if this String object lexicographically follows the argument string.
The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.

lexicographic ordering: If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both.

Why the 'two argument' version of this method doesn't work here and gives unpredictable output?

Arrays.binarySearch is producing the right results. I do not see any un-expected results.
sa has sa[0] = four, sa[1] = one, sa[2] = three, sa[3]= two and for overloaded binarySearch method right output is produced.

MySQL Blog
http://mysqlearner.blogspot.com/
Astha Sharma
Ranch Hand

Joined: Oct 15, 2011
Posts: 244

Thanks Anayonkar Shivalkar and Zeeshan Sheikh for the explanation.
I was not considering that it's "Binary Search". It would not need the Comparator as argument it it would be method performing linear search and I was thinking of it as lenier search algorithm, thats why got confused. My mistake

I agree. Here's the link: http://aspose.com/file-tools

subject: binarySearch() method of Arrays