Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

BinarySearching an Array sorted in descending order

 
O. Ziggy
Ranch Hand
Posts: 430
Android Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 430
Android Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 12097
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
O. Ziggy
Ranch Hand
Posts: 430
Android Debian VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic