About Collections.binarySearch method
Hi, can someone explain me why this code doesn't compile?
publicclass MyObjectimplements Comparable{
privateint i;
public MyObject(int i){
this.i = i;
}
publicint getTheInt(){
return i;
}
publicint compareTo(Object o){
MyObject obj = (MyObject)o;
if(obj.getTheInt() > this.getTheInt())
return 1;
elseif(obj.getTheInt() < this.getTheInt())
return -1;
return 0;
}
publicstaticvoid main(String[] args){
List<MyObject> objects=new ArrayList<MyObject>();
MyObject o1 =new MyObject(5);
MyObject o2 =new MyObject(6);
Collections.sort(objects);
MyObject found = Collections.binarySearch(objects, o1);
}
}
The error is this
C:\JSP Apps\ClienteTOARS\src\clientetoars\gui\MyObject.java:44: cannot find symbol
symbol : method binarySearch(java.util.List<clientetoars.gui.MyObject>,clientetoars.gui.MyObject)
location:class java.util.Collections
MyObject found = Collections.binarySearch(objetos, o1);
I really don't know what have I done wrong :(
Just an aside on binary search:
In this java.sun.com "Rock Star" interview with Josh Bloch:
http://java.sun.com/javaone/sf/2007/articles/rockstar_bloch.jsp
It is mentioned that there was bug in most binary search algorithms,
perhaps for the past 25 years!
Details here: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Oh, the error is that you didn't make use of the fact that Comparable is generic:
import java.util.*;
public class MyObject implements Comparable<MyObject> {
private int i;
public MyObject(int i) {
this.i = i;
}
public int getTheInt() {
return i;
}
public int compareTo(MyObject obj) {
if(obj.getTheInt() > this.getTheInt())
return 1;
else if(obj.getTheInt() < this.getTheInt())
return -1;
return 0;
}
public static void main(String[] args) {
List<MyObject> objects= new ArrayList<MyObject>();
MyObject o1 = new MyObject(5);
MyObject o2 = new MyObject(6);
Collections.sort(objects);
int found = Collections.binarySearch(objects, o1);
}
}
> Just an aside on binary search:
>
> In this java.sun.com "Rock Star" interview with Josh
> Bloch:
>
> http://java.sun.com/javaone/sf/2007/articles/rockstar_
> bloch.jsp
>
> It is mentioned that there was bug in most binary
> search algorithms,
> perhaps for the past 25 years!
>
> Details here:
> http://googleresearch.blogspot.com/2006/06/extra-extra
> -read-all-about-it-nearly.html
That's certainly good to know about. I think I will write my own binarySearch with the 'mid' value correction, although I don't think in my case this bug will appear, because my list of objects will never be larger than Integer.MAX_VALUE / 2 (where the bug might appear)
Message was edited by:
shittybytes
public int compareTo(MyObject obj) {
if(obj.getTheInt() > this.getTheInt())
return 1;
else if(obj.getTheInt() < this.getTheInt())
return -1;
return 0;
}
Just stared at this a little harder. This is opposite the usual ordering:
1 comes before 2, etc... Are you sure this is what you want?
I would write a utility method to compare ints, since if you use it once,
you're bound to use it again:
public int compareTo(MyObject obj) {
return Utiltiies.compare(this.getTheInt(), obj.getTheInt());
}
> //my crappy code
> Just stared at this a little harder. This is opposite
> the usual ordering:
> 1 comes before 2, etc... Are you sure this is what
> you want?
I wrote the MyObject class just to show an example of the binarySearch problem, because the class that i'm using is a little bit larger (and doesn't use ints to compare each other), the real one just compares dates with the Date class compareTo method, so it's not some big deal anyway :P
