package com.thealgorithms.searches;
import com.thealgorithms.devutils.searches.MatrixSearchAlgorithm;
/**
* The search is for any array which is sorted row and column-wise too. For ex :
* {{10, 20, 30, 40},
* {15, 25, 35, 45},
* {18, 28, 38, 48},
* {21, 31, 41, 51}}
*
* This array is sorted in both row and column manner.
* In this two pointers are taken, the first points to the 0th row and the second one points to end
* column, and then the element corresponding to the pointers placed in the array is compared with
* the target that either its equal, greater or smaller than the target. If the element is equal to
* the target, the co-ordinates of that element is returned i.e. an array of the two pointers will
* be returned, else if the target is greater than corresponding element then the pointer pointing
* to the 0th row will be incremented by 1, else if the target is lesser than the corresponding
* element then the pointer pointing to the end column will be decremented by 1. And if the element
* doesn't exist in the array, an array
* {-1, -1} will be returned.
*/
public class RowColumnWiseSorted2dArrayBinarySearch implements MatrixSearchAlgorithm {
@Override
public <T extends Comparable<T>> int[] find(T[][] matrix, T key) {
return search(matrix, key);
}
public static <T extends Comparable<T>> int[] search(T[][] matrix, T target) {
int rowPointer = 0; // The pointer at 0th row
int colPointer = matrix.length - 1; // The pointer at end column
while (rowPointer < matrix.length && colPointer >= 0) {
int comp = target.compareTo(matrix[rowPointer][colPointer]);
if (comp == 0) {
return new int[] {rowPointer, colPointer};
} else if (comp > 0) {
rowPointer++; // Incrementing the row pointer if the target is greater
} else {
colPointer--; // Decrementing the column pointer if the target is lesser
}
}
return new int[] {-1, -1}; // The not found condition
}
}