Big Moose Saloon
 Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies Register / Login

# BinarySearching an Array sorted in descending order

O. Ziggy
Ranch Hand

Joined: Oct 02, 2005
Posts: 430

According to the documentation:

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

Searches the specified array for the specified object using the binary search algorithm. 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. If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Does the above mean that the Arrays.binarySearch method can only be used when the Array is sorted in ascending order?

I tested it as shown below

output:

-5 puts the insertion point to at element with value c which is correct. (i.e. -4-1).
Why is the documentation saying that the array must be sorted in ascending order?

O. Ziggy
Ranch Hand

Joined: Oct 02, 2005
Posts: 430

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.

What does the "According to the specified comparator" mean?
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11955

20

you can create your own comparater, with its own logic as to what the correct 'sort' order is.

I might create a comparator that sorts the runners of a race by the place they came in, so that the first place runner is first in the list, etc. In other words, the list would be 1,2,3,4.

However, I may create another comparator that sorts bank balances, with the greatest listed first. So, a balance of \$4 would be ranked 1st, a balance of \$3 would be second, a balance of \$2 listed third, and \$1 listed fourth.

What is important is that the list be sorted according to some logic. what that logic is is implementation specific.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
O. Ziggy
Ranch Hand

Joined: Oct 02, 2005
Posts: 430

So the mention of "ascending order" is not referring to the situation where elements must be sorted from "small to big" or "a to z" or "1 to 10" etc.

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

subject: BinarySearching an Array sorted in descending order