Having problem with Arrays.binarySearch()

[xEnOn]

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:

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!

[oliver_watkins]

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

[xEnOn]

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.

[DarrylBurke]

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

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

[dpspine420]

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

[sunde887]

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.

[xEnOn]

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:

		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

0
2
1

instead of

0
1
2

[sunde887]

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?

[xEnOn]

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.

[xEnOn]

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.

[sunde887]

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.

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.

[dpspine420]

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

[DarrylBurke]

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.

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

[xEnOn]

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