I have a 2D integer array [n][3] and a target value. I sort the array using

Arrays.sort(arr, (a,b)->Integer.compare(a[1],b[1]));

How can I use Arrays.binarySearch and a custom comparator to search arr along index 1 for a target value? Something that could replace the following:

   int binSearch(int[][] arr, int target) {
      int low=0, high=arr.length-1;
      while( low < high ) {
         int mid=(low high)/2;
         if( arr[mid][1] == target ) {
            return i;
         }    
         else if( arr[mid][1] < target {
            low=mid 1;
         }
         else {
            high=mid-1;
         }
      }
      return -(low 1);
   }

EDIT: Arrays.sort works how I need it to - my initial array for example {{1,3,5},{7,1,6},{4,2,1}} sorts on the middle value to {{7,1,6},{4,2,1},{1,3,5}}

I thought I could write a similar expression for Arrays.binarySearch where each element (1x3) of the array is compared to a target integer. Something like:

int idx = Arrays.binarySearch(arr, target, (a,b)->Integer.compare(a[1],b));

I can't really use the same comparator as in the sort because they are different types - the search array is an array of 1x3 sized elements and my target is a single integer. I need to do a binary search.

CodePudding user response：

I think I better understand your case now.

Maybe once you've ordered the matrix as you've done, you can extract an array populated with the middle elements and then apply the binary search on it. Although, I don't really know your use case and how many elements you're handling, it might be too expensive...

int vetMiddleCol[] = IntStream.range(0, mat.length)
                .boxed()
                .mapToInt(i -> mat[i][1])
                .toArray();

int index = binarySearch(vetMiddleCol, target);

At that point, the index returned from the binary search will correspond to the element mat[index][1].

CodePudding user response：

Static method Arrays.binarySearch() has the following declaration:

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

Where T is the type of the elements in the array. In this case, it happens to be int[].

The important distinction between your method binSearch() and Arrays.binarySearch() is that your method expects an int argument target, meanwhile you need to pass int[] into binarySearch().

Since the required comparator needs only the second element (i.e. at index 1) of the array, the other elements of the key can have any value. Therefore, an array of two elements, like that

new int[]{0, target} // the first value, is arbitrary

will be a sufficient in order to utilize the built-in binarySearch().

int index = Arrays.binarySearch(source, new int[]{0, i}, comparator);

To define a comparator, you might make use of static methods comparing() and comparingInt() of the Comparator interface introduced with Java 8.

With that, the code bowls down to a couple of lines, and might be written like that:

public static void main(String[] args) {
    int[][] source = {{1, 3, 5}, {7, 1, 6}, {4, 2, 1}};
    
    Comparator<int[]> bySecondElement = Comparator.comparingInt(arr -> arr[1]);
    
    Arrays.sort(source, bySecondElement);
    
    for (int i = 0; i < 4; i  ) { // searching for arrays having a value of i as second element
        int index = Arrays.binarySearch(source, new int[]{0, i}, bySecondElement);
        System.out.printf("target: %d\tindex: %d\n", i, index);
    }
}

Output

target: 0   index: -1   // no such element
target: 1   index: 0    // {7, 1, 6}
target: 2   index: 1    // {4, 2, 1}
target: 3   index: 2    // {1, 3, 5}