aspose file tools*
The moose likes Beginning Java and the fly likes Java Comparators Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Java Comparators" Watch "Java Comparators" New topic
Author

Java Comparators

Adi Sharma
Ranch Hand

Joined: May 18, 2009
Posts: 33
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

Joined: Oct 13, 2005
Posts: 40052
    
  28
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

Joined: Aug 31, 2004
Posts: 11343

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.


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19785
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
krishna kanthgaru
Greenhorn

Joined: Feb 12, 2007
Posts: 17
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


no signature ... i am not a celebrity yet
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
Krishna Kanthgaru, welcome to JavaRanch
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Java Comparators