• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binarysearch and comparator  RSS feed

 
Shouvik Bhattacharya
Ranch Hand
Posts: 40
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Guys,

Can somebody please explain me that if an array has been sorted using a comparator then why is it necessary to pass on that comparator to the binaryserach method. What I want to know is that how come the presence of a comparator reference affect the way the algorithm works? I don't know from where this question struck me so just felt like asking for some guidance.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shouvik Bhattacharya wrote:
Can somebody please explain me that if an array has been sorted using a comparator then why is it necessary to pass on that comparator to the binaryserach method. What I want to know is that how come the presence of a comparator reference affect the way the algorithm works? I don't know from where this question struck me so just felt like asking for some guidance.


Hint: If you don't use a comparator to sort an array, how does the array get sorted? meaning what other options does the sorting algorithm have to compare the elements of the array?

Henry
 
Shouvik Bhattacharya
Ranch Hand
Posts: 40
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Henry,

Well, if I don't use a comparator then say for example if i have

and I sort this without any custom rules for comparison using a comparator then the array gets sorted in ascending order. Which is the natural order. I mean do you mean to say that while searching the binary search will use the rules in the compare method to find the element with respect to a given key? Or maybe if the Key is not comparable to the elements of the array then their might be a possible chance of ClassCastException
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shouvik Bhattacharya wrote:
Well, if I don't use a comparator then say for example if i have

and I sort this without any custom rules for comparison using a comparator then the array gets sorted in ascending order. Which is the natural order. I mean do you mean to say that while searching the binary search will use the rules in the compare method to find the element with respect to a given key? Or maybe if the Key is not comparable to the elements of the array then their might be a possible chance of ClassCastException


First, when I said "if you don't use a comparator to sort an array", I didn't say with a different data type. The comparator is to sort Object arrays (after generics type erasure), so I was referring to Object arrays, and not int arrays... but yeah, assuming that the objects are comparable, it will be in natural order.

So, if you use a comparator, and the ordering is different from the natural order -- how will the binary search code know that? Meaning if you use the version of the binary search that doesn't take a comparator, why should it assume that it is in any order but the natural order? This is why you need to pass the comparator.

Henry

 
Shouvik Bhattacharya
Ranch Hand
Posts: 40
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Henry...!!
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shouvik Bhattacharya wrote:Thank you Henry...!!

I hope this isn't overload for you, but I actually like Comparators a lot - so much so that I've created a special one for myself, viz:And to create one for, say, a String:
Comparator<String> defaultOrder = new NaturalOrder<String>();

It might seem a bit silly; but the nice thing about it is that it allows you to use Comparators everywhere, rather than deciding whether to use one based on whether a type is Comparable or not.

HIH

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!