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