the method is:

public static boolean search(int matrix[][], int key)

the method will return true if key is found in the matrix, the matrix size will be always n x n , the matrix is circular sorted and here is example how it looks like for 4x4 example

Run time efficiency must be lower than O(n^2) , aiming for O(n log n)

This is the structure I tried to imply,the code isn`t working it just my thought process

public static boolean search1 (int [][] matrix, int num) 
{

    int ROWS = matrix.length;
    int COLS = matrix[0].length; 
    int end = COLS * ROWS; 
    int first_quarter_pivot = matrix[0][0];
    int second_quarter_pivot = matrix[0][i];
    int third_quarter_pivot = matrix[i][0];
    int fourth_quarter_pivot = matrix[i][i];
      
       if(num < first_quarter_pivot)
       // if num smaller than first pivot binary search first quarter,if not found return false
       binarySearch( );
       
       if(num < second_quarter_pivot)
       binarySearch( );
       // if num smaller than second pivot binary search second quarter ,if not found return false
       if(num < third_quarter_pivot )
       binarySearch( );
       // if num smaller than third pivot binary search third quarter ,if not found return false
       // else search fourth quarter
       else
        binarySearch( );
       // return false if nothing found
     
    }

I cant find the pivots to split the matrix to 4 quarters,I want to find the edges of each quarter,and I want to find in each quarter the bottom left corner which il compare num against in each quarter

hope I was clear,ty in advance.

CodePudding user response：

Good question

A trick we normally use to limit a grid, is passing in the starting row index, ending row index, starting column index, ending column index.

Your header will become

public boolean search(int[][] matrix, int key, int startRow, int endRow, int startColumn, int endColumn){

The first call, startRow startColumn will be 0, the endRow and endColumn will be n-1 Every time you identify which quarter the key falls in, shrink these values accordingly for the next recursive call

Steps

first find n, which is matrix.length.

Then using n to find the row and column for the number(s) in the middle of the grid.

If n is odd (etc 5x5), then there will be a number in the middle grid, its index is n=5, 5/2 = 2, get its value by matrix[2][2]. But I double this circular sort work on odd number matrix.

If n is even (etc 4x4), you don't have a number in the middle this time, then you need to find the 4 biggest number in each quarter.

Then use the key to compare with this middle number(s) to find which quarter. Using your example, if key is 55, how do you know which quarter it is in?

First compare with the biggest value in first quarter (6), if the key is less than 6, then it is first quarter, then compare with biggest value in second quarter (15), if it is less than 15 then it is in second quarter. Repeat for third quarter and fourth quarter.

The algorithm to find the index for the biggest number in the first quarter is matrix[value-1][startColumn] = 6, value is n/2 = 4/2 = 2

For second quarter, the matrix[value-1][value] = 15 happens to be the biggest number in second quarter, lucky.

For third quarter, index for the biggest number is matrix[endRow][startColumn] = 60

For fourth quarter, index for the biggest number is matrix[endRow][value] = 30

After you limited the quarter, you should recursively call this function again