Hey there! Let's work through this problem step by step. First, let's recap the key constraints we have:

• We're dealing with an n×n square matrix that's "circularly-sorted" as per your definition: every element in Quarter 1 (Q1) is strictly smaller than every element in Quarter 2 (Q2), which is strictly smaller than every element in Quarter 3 (Q3), which is strictly smaller than every element in Quarter 4 (Q4).
• We need an efficient search method to check if a given number exists in the matrix.

First, let's clarify the quadrant divisions for an n×n matrix:

• Q1 (Top-left): Rows 0 to mid-1, Columns 0 to mid-1 (where mid = n / 2, integer division)
• Q2 (Top-right): Rows 0 to mid-1, Columns mid to n-1
• Q3 (Bottom-right): Rows mid to n-1, Columns mid to n-1
• Q4 (Bottom-left): Rows mid to n-1, Columns 0 to mid-1

Given the strict ordering between quadrants, we can use the boundary values of each quadrant to quickly narrow down which quadrant (if any) could contain our target number. Since the matrix is guaranteed to be valid, we know:

• Q1's maximum value < Q2's minimum value
• Q2's maximum value < Q3's minimum value
• Q3's maximum value < Q4's minimum value

Approach #

1. Calculate matrix dimensions: Get the size n of the square matrix, then compute mid = n / 2.
2. Get quadrant boundary values: Extract the min/max values for each quadrant (since each quadrant is internally sorted—otherwise we couldn't get these bounds efficiently, which aligns with the "circularly-sorted" intent for performance).
3. Narrow down the target quadrant: Based on the target number, determine which quadrant it could possibly be in using boundary comparisons.
4. Search the target quadrant: Use binary search on the relevant quadrant. Since each quadrant is a sorted 2D submatrix, we can use either row-by-row binary search or a more efficient 2D binary search approach.

Solution Code #

import java.util.Arrays;

public class CircularSortedMatrixSearch {

    public static boolean search(int[][] mat, int num) {
        int n = mat.length;
        // Safeguard even though problem states mat is non-empty
        if (n == 0) return false;
        
        int mid = n / 2;
        
        // Handle trivial 1x1 matrix case
        if (n == 1) {
            return mat[0][0] == num;
        }
        
        // Grab boundary values for each quadrant (assuming row-wise sorted quadrants)
        int q1Max = mat[mid - 1][mid - 1];
        int q2Min = mat[0][mid];
        int q2Max = mat[mid - 1][n - 1];
        int q3Min = mat[mid][mid];
        int q3Max = mat[n - 1][n - 1];
        int q4Min = mat[mid][0];
        int q4Max = mat[n - 1][mid - 1];
        
        // Check which quadrant could contain the target
        if (num <= q1Max) {
            return searchSortedSubmatrix2D(mat, num, 0, mid - 1, 0, mid - 1);
        } else if (num >= q2Min && num <= q2Max) {
            return searchSortedSubmatrix2D(mat, num, 0, mid - 1, mid, n - 1);
        } else if (num >= q3Min && num <= q3Max) {
            return searchSortedSubmatrix2D(mat, num, mid, n - 1, mid, n - 1);
        } else if (num >= q4Min && num <= q4Max) {
            return searchSortedSubmatrix2D(mat, num, mid, n - 1, 0, mid - 1);
        }
        
        // Target is outside all quadrant ranges
        return false;
    }
    
    // Efficient 2D binary search helper: treats submatrix as a sorted 1D array
    private static boolean searchSortedSubmatrix2D(int[][] mat, int num, int startRow, int endRow, int startCol, int endCol) {
        int colCount = endCol - startCol + 1;
        int totalElements = (endRow - startRow + 1) * colCount;
        int left = 0;
        int right = totalElements - 1;
        
        while (left <= right) {
            int midIdx = left + (right - left) / 2;
            // Convert 1D index to 2D coordinates
            int row = startRow + midIdx / colCount;
            int col = startCol + midIdx % colCount;
            
            if (mat[row][col] == num) {
                return true;
            } else if (mat[row][col] < num) {
                left = midIdx + 1;
            } else {
                right = midIdx - 1;
            }
        }
        return false;
    }
    
    // Alternative helper: row-by-row binary search (easier to read, slightly less efficient)
    private static boolean searchSortedSubmatrixRowWise(int[][] mat, int num, int startRow, int endRow, int startCol, int endCol) {
        for (int i = startRow; i <= endRow; i++) {
            int[] rowSegment = Arrays.copyOfRange(mat[i], startCol, endCol + 1);
            int searchResult = Arrays.binarySearch(rowSegment, num);
            if (searchResult >= 0) {
                return true;
            }
        }
        return false;
    }
}

Explanation #

• Time Complexity: The 2D binary search helper (searchSortedSubmatrix2D) runs in O(log n) time—we treat the target quadrant as a single sorted 1D array, so the search scales with the log of the total number of elements in the quadrant. The row-wise helper has a time complexity of O(n log n), which is still efficient but slightly slower for large matrices.
• Space Complexity: Both approaches use O(1) additional space (excluding the input matrix), which is optimal for this problem.
• Assumptions: We assume each quadrant is row-wise sorted—this is a necessary extension to make efficient search possible, and aligns with the problem's focus on performance and the "circularly-sorted" definition.

内容的提问来源于stack exchange，提问作者Ofek .D