aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes BinarySearching an Array sorted in descending order Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "BinarySearching an Array sorted in descending order" Watch "BinarySearching an Array sorted in descending order" New topic
Author

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: 11475
    
  16

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