• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Java Comparators

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Marshal
Posts: 79151
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Krishna Kanthgaru, welcome to JavaRanch
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic