Search in a circularly-sorted array Java

user_9351897 0
Viewed 106

i really got stuck on this and i'd love your help.
I'm trying to write a method with the signature:

public static boolean search (int [][] mat, int num)

The method gets as parameters two-dimensional array that is circularly-sorted, and a value to search for num. If the value num is in the mat array, the method returns true. If the num value is not in the mat array, the method returns false.

example for circularly-sorted array

The array is circular if all the values in Quarter 1 are really smaller than all those in Quarter 2, those in Quarter 2 are really smaller than all those in Quarter 3, and those in Quarter 3 are really smaller than all those in Quarter 4.

For example, the following array is circularly-sorted:

a bigger example of a circularly-sorted array

If the array mat is the array drawn above, and the number num is 22, the method returns the value true.
If the array mat is the array drawn above, and the number num is 23, the method will return the value false

The conditions:

  • The array is quadratic two-dimensional, meaning that the number of rows and columns is equal
  • The mat array is not null and is circularly-sorted. You do not need to check this.
  • The method should be as effective as possible, both in terms of time complexity and In terms of memory complexity.
java
1 Answers

The construction of this sort is such that the smallest element of each quarter is in the top left and the largest is in bottom left. You can check in which quarter the searched for element should be located and repeat the search in sub-quarters of that quarter.

An example implementation:

private static boolean search(int[][] mat, int num) {
    if (!square(mat)) {
        throw new IllegalArgumentException("matrix is not square");
    }
    
    int dim = mat.length;
    int topRow = 0;
    int leftColumn = 0;
    
    while (dim > 1) {
        if (dim % 2 != 0) {
            throw new IllegalArgumentException("matrix dimension is not a power of two");
        }
        
        int qdim = dim / 2; // quarter dimensions
        
        // Order of checks is important.
        if (num >= mat[topRow + qdim][leftColumn]) {
            // has to be in the bottom left quarter
            topRow += qdim;
        } else if (num >= mat[topRow + qdim][leftColumn + qdim]) {
            // has to be in the bottom right quarter
            topRow += qdim;
            leftColumn += qdim;
        } else if (num >= mat[topRow][leftColumn + qdim]) {
            // has to be in the top right quarter
            leftColumn += qdim;
        }

        // If all the conditions above give false, it's in the top left quarter
        // and topRow and leftColumn don't change.
        
        dim = qdim;
    }
    
    return mat[topRow][leftColumn] == num;
}

Full code

user_176952110
Related