Enthuware

I find the answer explanations confusing. Isn't the comparator only used to determine the sort order and not equality of elements?

In this question Comparator has this method:

public int compare(Object o1, Object o2)
{
int s1 = ((String) o1).length();
int s2 = ((String) o2).length();
return s1 - s2;
}
}

and the array is static String[] sa = { "d", "bbb", "aaaa" };

If binarySearch() is used to search for "c", I agree that the answer will be 0 but that is because "c" comes before "d" in natural ordering. If the first element had been "D" then "c" would have come after that. The explanation just says "there is only one string of length 1 in sa, and it is at index 0." Sure, if we added a string of length 1 and sorted the array, it would be next to the only length 1 element ("d") but the explanation seems to say "the new length 1 element" would added at index 0. Can't it be added at index 1 as well? I would really appreciate an explanation.

Thanks!

Hello,

In the given question, we are overriding the "natural" ordering of the elements of the array using the custom comparator. The order specified by the comparator is the new natural order now. So, when you say,

"c" comes before "d" in natural ordering

, that is not correct because as per the given compatator, "c" and "d" (and "D") are all exactly equal.

Therefore, when you search for "c" in the given array, the search is successful (and not unsuccessful as you seem to be thinking) because the array does contain "c" (Remember, "d" is equal to "c"). And "c" is at index 0 in the array. Hence, the search returns 0.

If you had multiple strings of length 1 in the array, for example, { "D", "d", "d", "f", "g", "bbb", "aaaa" };
the search would be successful but the return value could be anything between 0 and 4 (both inclusive) because "D", "d", "d", "f", "g" are all equal and are equal to "c". (All are of length 1).

HTH,
Paul.

ETS User wrote: If binarySearch() is used to search for "c", I agree that the answer will be 0 but that is because "c" comes before "d" in natural ordering.

No, the answer is 0 not because "c" comes before "d", but because "c" and "d" are equal and the binarySearch finds "c" in the array at index 0. In other words, it is not returning the insertion point (which would have been a negative number actually), it is returning the index of the element that is equal to "c", which is 0.

ETS User wrote: If the first element had been "D" then "c" would have come after that.

No, it would still return 0 because "c" and "D" are equal as well. "c" doesn't come after or before "D". "c" and "D" are "equal".

HTH,
Paul.

public int compare(Object o1, Object o2) Isn't the parameter should be specific class instead of Object?

public static <T> int binarySearch​(T[] a, T key, Comparator<? super T> c)
The array must be sorted into ascending order according to the specified comparator (as by the sort(T[], Comparator) method) prior to making this call. If it is not sorted, the results are undefined.

Please sort the array in the sample code or maybe explain that it will be sorted with MyStringComparator before binarySearch is called.

The search is being done using an instance of MyStringComparator and the input array sa is already sorted according to this Comparator. So, there is no issue here.

I run this code locally and returns -1 and not 0.

So this

Arrays.binarySearch(sa, "c", new MyStringComparator()); will return -1.

should be true.

Please check your code. The following code (as given in the question) prints 0 and not -1.