Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Java Comparators

 
Adi Sharma
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys

I was reading :

"If the collection/array you want to search was sorted using a Comparator, it
must be searched using the same Comparator, which is passed as the second
argument to the binarySearch() method"


I was wondering as to why do we need to pass the same comparator to the binarySearch() method???

Thanks a lot
Aditya Sharma
 
Campbell Ritchie
Sheriff
Posts: 48910
58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You have to use the Comparator to decide whether you have found the sought element yet.

Somebody else, please answer. I am sure you would give a better answer than I have
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A Comparator compares elements based on its own logic. For example, one Comparator might put 1 before 2. But a different Comparator might put 2 before 1, depending on how it's coded.

So if a collection/array is sorted using a Comparator, then an instance of the same Comparator needs to be used when conducting a binary search. Otherwise, the logic of the search might not be consistent with the logic that was used to sort the collection/array.

Note: I don't think it needs to be the same Comparator instance. It just needs to be an instance of the same Comparator class.
 
Rob Spoor
Sheriff
Pie
Posts: 20526
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not even that. The only requirement is that, for sorting Comparator sort and searching Comparator search and any two objects x and y:
- if sort.compare(x, y) < 0 then search.compare(x, y) < 0
- if sort.compare(x, y) = 0 then search.compare(x, y) = 0
- if sort.compare(x, y) > 0 then search.compare(x, y) > 0

In other words, the two Comparators impose the same ordering. Of course using instances of the same class will usually do that, unless instances use instance fields in their sorting decision. If you use the same instance then the above three rules are true by default. Unless again it uses instance fields and those fields are changed.
 
krishna kanthgaru
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i believe when they said "must be searched using the same Comparator" they mean that would be the comparator best built to exploit the sorted order.

i don't see any other logical reason.

Adi Sharma wrote: Hi guys

I was reading :

"If the collection/array you want to search was sorted using a Comparator, it
must be searched using the same Comparator, which is passed as the second
argument to the binarySearch() method"


I was wondering as to why do we need to pass the same comparator to the binarySearch() method???

Thanks a lot
Aditya Sharma
 
Campbell Ritchie
Sheriff
Posts: 48910
58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Krishna Kanthgaru, welcome to JavaRanch
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic