Results 1 to 14 of 14
  1. #1
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Question 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;
    		}
    	}
    }
    It seems like sometimes it can find a value but sometimes it cannot. Like for in the case to find the integer array of {8,9}, it returns a negative index.

    Am I doing this correctly?

    Thanks!

  2. #2
    Join Date
    May 2011
    Location
    Munich
    Posts
    15
    Rep Power
    0

    Default

    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 fine
    read my blog : www.blue-walrus.com

  3. #3
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    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.

  4. #4
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,458
    Rep Power
    20

    Default

    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;
        }
      }
    }
    db

  5. #5
    dpspine420's Avatar
    dpspine420 is offline Member
    Join Date
    May 2011
    Posts
    9
    Rep Power
    0

    Default

    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

  6. #6
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Quote Originally Posted by dpspine420 View Post
    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
    Well intentioned but incorrect. As db stated, the binary search uses indexes where the end location is exclusive. So 0, 2, checks array elements 0 and 1. As he changed it in the code you only really need to have it check from 0 - the arrays length.

  7. #7
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    Quote Originally Posted by DarrylBurke View Post
    Read the API for Arrays#binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)


    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[]>?

    db

    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()));
    The output is
    Java Code:
    0
    2
    1
    instead of
    Java Code:
    0
    1
    2
    Last edited by xEnOn; 05-10-2011 at 01:35 PM.

  8. #8
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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?

  9. #9
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    Quote Originally Posted by sunde887 View Post
    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?
    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.

  10. #10
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    Quote Originally Posted by dpspine420 View Post
    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
    Did you mean like passing it as array together with its key position? So from an int[2] becomes an int[3], which the first element of index zero is the position of the key? Other than that, I am not sure how I can pass in a key together into the compare method.

  11. #11
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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);
    }
    There may be some errors in this, but it's a general idea. Other people may have a more efficient way to do this.

  12. #12
    dpspine420's Avatar
    dpspine420 is offline Member
    Join Date
    May 2011
    Posts
    9
    Rep Power
    0

    Default

    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.

  13. #13
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,458
    Rep Power
    20

    Default

    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));
      }
    }
    db

  14. #14
    xEnOn is offline Member
    Join Date
    May 2011
    Posts
    8
    Rep Power
    0

    Default

    ahh... great idea!
    thanks everyone for the suggestions! these are very helpful!
    thanks a lot! :D

Similar Threads

  1. Problem with arrays
    By Viper in forum New To Java
    Replies: 7
    Last Post: 10-07-2010, 03:49 PM
  2. Arrays.asList(...) Problem
    By plm-pusik in forum New To Java
    Replies: 2
    Last Post: 09-18-2010, 02:12 AM
  3. SortedSet and Collections.binarySearch
    By ninoid in forum New To Java
    Replies: 4
    Last Post: 03-22-2010, 04:28 PM
  4. loop problem-arrays
    By ester in forum New To Java
    Replies: 0
    Last Post: 02-02-2010, 10:44 PM
  5. Replies: 4
    Last Post: 02-13-2009, 08:42 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •