This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Collections.binarySearch Question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Collections.binarySearch Question" Watch "Collections.binarySearch Question" New topic
Author

Collections.binarySearch Question

Clay Chow
Ranch Hand

Joined: Nov 09, 2008
Posts: 35
Can a list be sorted & searched if the array elements implement Comparable only ? The below code creates an ArrayList of "Sheep" objects (which implement Comparable). However, I get the below error when I compile. The code compiles when I substitute Integer in for Sheep; which leads me to think it works because Integers have a natural order. But would implementing Comparable make any object have a natural order?

Thanks!


C:\SCJP\del>javac Jav.java
Jav.java:55: cannot find symbol
symbol : method binarySearch(java.util.List<Sheep>,Sheep)
location: class java.util.Collections
int a = Collections.binarySearch(pq, new Sheep("Rack"));
^
1 error

Harvinder Thakur
Ranch Hand

Joined: Jun 10, 2008
Posts: 231
Originally posted by Clay Chow:

However, I get the below error when I compile.


The code that you have given compiles & runs fine.
May be you've given the wrong code and also do mention the source of your code.


thanks
Harvinder
Clay Chow
Ranch Hand

Joined: Nov 09, 2008
Posts: 35
curious.
I am definitely getting an error (using 1.6.0_07).
I would agree that there should be no error, but am curious as to what the result would be. I wrote this to see how the binarySearch method works: since the Sheep.equals method always returns true, I assume that it will return the index of any element that matches.




Source:
Extended code from Osbourne McGraw SCJP 6 Study Guide. Although the question I'm asking is not the same.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38075
    
  22
It ought to be implements Comparable<Sheep> . . .
Then you can have Sheep as the type of the parameter to the compareTo method. You can then forget about the class casting, too.
Telling the compiler to implement Comparable<T> will lead the compiler to "believe" that this class has a "natural order."

You realise that two Sheep with the same name length will be left alone by the sort algorithm?
And imagine what will happen if you have a flock of 976 sheep, all with 6 letters in their name. The sort method will leave them all in the same order and the binary search will have no chance of finding them.

Suggest that, if you are comparing by the name field, and name is a String, and String already implements Comparable<String>, you could try changing the compareTo method to read

return name.compareTo(other.name);

You ought to have a look at the Object class and read about equals.
You will be in a situation where woolly.equals(obj) and !obj.equals(woolly). The sort and search methods are dependent on the compare, equals (and maybe hashCode) methods being implemented correctly.

The way binary search works is that it finds the middle element by taking myArray.length / 2; if that is equal, then eureka!
If it is "less" (compareTo returns negative) it tries middle / 2, otherwise it tries (middle + length) / 2 and keeps going until it runs out of options or finds something.
What happens if compareTo() returns 0 and equals returns false, I am not sure. Maybe it returns a negative result.
Clay Chow
Ranch Hand

Joined: Nov 09, 2008
Posts: 35
Thanks for your help!

But your answer begs one more question: why does implementing Comparable<T> but not just Comparable, lead the compiler to "believe" that this class has a "natural order." ?


This would lead me to believe any object that implements Comparable<Sheep> would be accepted in that binarySearch argument. But that is not the case.
So I guess the compiler is looking for a Sheep object as well.
Harvinder Thakur
Ranch Hand

Joined: Jun 10, 2008
Posts: 231
Originally posted by Campbell Ritchie:

What happens if compareTo() returns 0 and equals returns false, I am not sure. Maybe it returns a negative result.


In the code snippet in the OP, if i make the equals() method to return "false" then the result is still the same even if compareTo() returns *0* which it will because of the way compareTo() logic has been written.
I believe the reason is that the equals() method is not used in the binarySearch or sort. It's only the compareTo() method that is used.
Please correct me if i'm wrong.

Originally posted by Campbell Ritchie:

Telling the compiler to implement Comparable<T> will lead the compiler to "believe" that this class has a "natural order."

Can you please elaborate on the above statement regarding "natural order"?

I agree with the rest of the explanation given by Campbell regarding how one should correctly implement the compareTo() method.

@Clay: I am using java version "1.5.0_05" and the code compiles and gives the output:

1
[Bad, Bill]
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38075
    
  22
Read the API for Comparable<T> which used to be called Comparable. It there tells you that Comparable (or Comparable<T> is used for classes which have a "natural order." Whoever wrote the sort method which takes Comparable<...> as a parameter wrote it on the assumption that its parameters have a natural order, so when it is compiled and executed, that is on the assumption that it has a natural order.
Whoever wrote the compiler did so on the assumption that Comparable<T> represents a natural order. The same applied to Comparable when it was called Comparable rather than Comparable<T>.

If you put implements Comparable<...> on something which doesn't have a natural order, you needn't expect the correct results back.

I think the nearest you have to a natural order for sheep (do real sheep have a natural order) is in order of name.
Harvinder Thakur
Ranch Hand

Joined: Jun 10, 2008
Posts: 231
@Campbell:
Thanks for the explanation on natural order.
Can you please elaborate if and how the equals() method is used in the sort() and binarySearch() methods? Because as per my understanding equals() is not used in either of sort() or binarySearch()?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38075
    
  22
I don't think equals() is used in sort().
I think (but I am not sure) that methods which identify an object in a Collection use the equals() method to signal that they have found it. You look in the Collection for an object called obj, and when your collection element returns true from obj.equals(element) or element.equals(obj), the method is programmed to assume it has "found it."

Find a file called src.zip in your Java installation folders, unzip it to a convenient location, find the java folder, then the util folder, then the Collections class, and you can read the code of the binarySearch method. That will confirm how the method works.
Harvinder Thakur
Ranch Hand

Joined: Jun 10, 2008
Posts: 231
Thanks a lot for the explanation Campbell. In fact, i did check up the Collections class source code and found that neither sort() nor binarySearch() use the equals() method. They both use the compareTo() method.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38075
    
  22
Aha. I never knew about it using compareTo. Thank you
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Collections.binarySearch Question
 
Similar Threads
Generic Types extending Abstract implementing Interface
page# 616 question# 10
puzzled by this question
K&B collection and generic question
Generics