Results 1 to 14 of 14
- 05-10-2011, 12:13 PM #1
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
Having problem with Arrays.binarySearch()
I am trying to make use of the Binary Search feature in the Arrays.utils package. It is just a simple search but I am search on a set of arrays. That's, I need to search an array of arrays. So I guess I have to create my own compare method. Here's what I have done:
PHP Code:public class MyClass implements Comparator<Object> { public static void main(String[] args) { Object[] coordinates = new Object[3]; int[] coord = {1, 2}; coordinates[0] = coord; int[] coord1 = {8,9}; coordinates[1] = coord1; int[] coord2 = {6, 7}; coordinates[2] = coord2; Arrays.sort(coordinates, new MyClass()); System.out.println(Arrays.binarySearch(coordinates, 0, 2, new int[]{8,9}, new MyClass())); } @Override public int compare(Object arg0, Object arg1) { int[] obj0 = (int[]) arg0; int[] obj1 = (int[]) arg1; if(obj0[0] == obj1[0] && obj0[1] == obj1[1]) { return 0; } else if(obj0[0]*obj0[1] < obj1[0]*obj1[1]) { return -1; } else { return 1; } } }
Am I doing this correctly?
Thanks!
- 05-10-2011, 12:31 PM #2
Member
- Join Date
- May 2011
- Location
- Munich
- Posts
- 15
- Rep Power
- 0
what determines the value returned in compare? I can understand that you are checking all the arrays for equality to return 0.
But what makes an array bigger than the other? You are multiplying all the elements. Should you be adding them maybe? {2,4} is bigger than {1,7} in your case.
Otherwise everything looks fineread my blog : www.blue-walrus.com
- 05-10-2011, 12:40 PM #3
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
In the compare method, I actually is not very concerned with who is smaller or larger since what I really need to to know if an array does exist in an array of arrays, ie: if an array say new int[] {3,4} is inside coordinates[] array or not.
I just used multiplying for no reason actually because I don't know how I should rank the array of coordinates. Also, I have tried adding them but it the Arrays.binarySearch still cannot find certain values in the coordinates[] array.
- 05-10-2011, 12:55 PM #4
Read the API for Arrays#binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
toIndex - the index of the last element (exclusive) to be searched
Your code is searching within the first two elements, which of course doesn't contain {8,9}.
Is there any reason you are using Comparator<Object> and not Comparator<int[]>?
Java Code:import java.util.Arrays; import java.util.Comparator; public class MyClass implements Comparator<int[]> { public static void main(String[] args) { int[][] coordinates = new int[3][]; int[] coord = {1, 2}; coordinates[0] = coord; int[] coord1 = {8, 9}; coordinates[1] = coord1; int[] coord2 = {6, 7}; coordinates[2] = coord2; Comparator<int[]> comparator = new MyClass(); Arrays.sort(coordinates, comparator); System.out.println(Arrays.binarySearch(coordinates, 0, 3, new int[]{8, 9}, comparator)); } @Override public int compare(int[] arg0, int[] arg1) { if (arg0[0] == arg1[0] && arg0[1] == arg1[1]) { return 0; } else if (arg0[0] * arg0[1] < arg1[0] * arg1[1]) { return -1; } else { return 1; } } }
- 05-10-2011, 01:01 PM #5
if you are just trying to find if the array exists you don't need to multiply you need to run a loop to check conditions. and what db said about an object vs a int[] so maybe for your compare method try passing a key/value along with changing it to an array for it to check. hope it helps
- 05-10-2011, 01:31 PM #6
- Join Date
- Jan 2011
- Location
- Richmond, Virginia
- Posts
- 3,068
- Blog Entries
- 3
- Rep Power
- 15
- 05-10-2011, 01:32 PM #7
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
Thanks! It could find the last element now after changing the toIndex value. I think you are right. I should use the Comparator<int[]> instead.
I realise there is something weird about the search with the sort.
In the documentation, it says that the array has to be sorted before it could do a binary search. I did try to do a binary search without sorting it and of course it couldn't find some of the values. But the thing with sorting is that it doesn't preserve the original position indexes of the array and returns the new sorted index positions.
So in a case like this:
PHP Code:int[][] coordinates = new int[3][]; int[] coord = {1, 2}; coordinates[0] = coord; int[] coord1 = {8,9}; coordinates[1] = coord1; int[] coord2 = {6, 7}; coordinates[2] = coord2; Arrays.sort(coordinates, new MyClass()); System.out.println(Arrays.binarySearch(coordinates, 0, 3, new int[]{1,2}, new MyClass())); System.out.println(Arrays.binarySearch(coordinates, 0, 3, new int[]{8,9}, new MyClass())); System.out.println(Arrays.binarySearch(coordinates, 0, 3, new int[]{6,7}, new MyClass()));
Java Code:0 2 1
Java Code:0 1 2
Last edited by xEnOn; 05-10-2011 at 01:35 PM.
- 05-10-2011, 01:35 PM #8
- Join Date
- Jan 2011
- Location
- Richmond, Virginia
- Posts
- 3,068
- Blog Entries
- 3
- Rep Power
- 15
Sort will re arrange the array contents. Think about it, can your sort 5 items without moving them? No, you can't and since sort actually effects the object state you are left with a changed array.
I am wondering, do you know why arrays must be sorted to perform binary searches?
- 05-10-2011, 01:49 PM #9
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
From my understanding, the array needs to be sorted because the binary search will essentially divide it into 2 lower and upper portions and then see which portion the element's key is in. And then further divide that portion recursively until it finds the actual element.
I understand that the array positions will be changed since I have done a sort. But maybe this doesn't benefit me in my current scenario, which I may have to sort the original positions of the elements in the array.
- 05-10-2011, 01:51 PM #10
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
- 05-10-2011, 02:05 PM #11
- Join Date
- Jan 2011
- Location
- Richmond, Virginia
- Posts
- 3,068
- Blog Entries
- 3
- Rep Power
- 15
You understand binary search well, although I'm sure it can be done iteratively as well as recursively.
If you really needed to keep the original array preserved you can create a second array that is sorted and searched. Then use the found value to index into the original array with indexOf.
Java Code:int[] x = {2, 1, 4, 5, 2, 3}; int[]y = x; Arrays.sort(y); int found = Arrays.binarySearch(y, 0, y.length, 3); int origIndex = 0; if(found > 0){ origIndex = Arrays.asList(x).indexOf(found); }
- 05-10-2011, 02:06 PM #12
Thats exactly what I was suggesting, so it can compare to that position/index to check if there is a value since you are just looking to see if it exists. But sunde887 has a better explanation along with a on idea on how you have already set it up
Last edited by dpspine420; 05-10-2011 at 02:11 PM.
- 05-10-2011, 03:03 PM #13
Or write a class that has a int[2] member (or just two ints) with an overridden equals(...) and add instances of this to a List where you can use List#contains(...).
Typed here, may have typos.Java Code:public class TwoInts { private final int int0; private final int int1; public TwoInts(int int0, int int1) { this.int0 = int0; this.int1 = int1; } public TwoInts(int... ints) { if (ints.length != 2) { throw new IllegalArgumentException("Array must have two elements"); } this.int0 = ints[0]; this.int1 = ints[1]; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj instanceof TwoInts) { TwoInts other = (TwoInts) obj; return int0 == other.int0 && int1 == other.int1; } return false; } public static void main(String[] args) { List<TwoInts> list = new ArrayList<TwoInts>(); list.add(new TwoInts(1, 2)); list.add(new TwoInts(new int[] {8, 9})); list.add(new TwoInts(6, 7)); TwoInts test = new TwoInts(8, 9); System.out.println("List contains test? " + list.contains(test)); System.out.println("Index of test? " + list.indexOf(test)); } }
- 05-10-2011, 06:04 PM #14
Member
- Join Date
- May 2011
- Posts
- 8
- Rep Power
- 0
Similar Threads
-
Problem with arrays
By Viper in forum New To JavaReplies: 7Last Post: 10-07-2010, 03:49 PM -
Arrays.asList(...) Problem
By plm-pusik in forum New To JavaReplies: 2Last Post: 09-18-2010, 02:12 AM -
SortedSet and Collections.binarySearch
By ninoid in forum New To JavaReplies: 4Last Post: 03-22-2010, 04:28 PM -
loop problem-arrays
By ester in forum New To JavaReplies: 0Last Post: 02-02-2010, 10:44 PM -
how does public static <AnyType extends Comparable<? super AnyType>> int binarySearch
By JordashTalon in forum New To JavaReplies: 4Last Post: 02-13-2009, 08:42 AM
Bookmarks