Searching an element in a row and column wise sorted matrix

First let me state the problem we will discuss in this post:  You are given a 2-D array of  nXn size with all the elements sorted in descending order row and column wise. You need to find a particular element in that array.
There may be lots of ways to solve this problem. I will discuss three ways to solve this problem using a
(i)linear search,
(ii)binary search,
(iii) binary search graph [ I know its bit confusing. Don't  go on the name ]



Before you start reading solutions I need to state that I have used 2-D array and matrix for the same purpose throughout the post and assumed that  the indexing starts from 0.
For each function used here, main function described under "Third Method"  can be used to call the respective functions commenting and un-commenting respective function calls.

Linear Search Method:
This approach is the most general approach. Only thing we need to keep in mind that we are dealing with 2-d array not an 1-d array. Just iterate through all the elements of the matrix
[ as we do in displaying  a matrix] and check whether the element exists or not. That's all.
As 2-d array is of size nXn, Its complexity will be  O(n²).
Here is the code:

void _2D_linear(int **mat, int size, int num)
{
 int i, j, flag;
 flag = 0;
 for (i = 0; i < size; i++) {
  for (j = 0; j < size; j++) {
   if (mat[i][j] == num) {
    flag = 1;
    break;
   }
  }
  if (flag == 1)
   break;
 }
 if (flag == 0)
  printf("Data not found in the matrix!!!\n");
 else
  printf("Data found at position :%d,%d\n", i + 1, j + 1);
}

Binary search Method: 
This approach is little better than the previous approach. What we can do is to treat each row of the matrix as an 1-d array and perform a binary search on that 1-d array. If the required number is found then stop the procedure and declare the position otherwise continue the binary search on each row and if after performing binary search on each row of the matrix required element is not found then declare that required number is not found on the matrix.
This will require n binary searches for  n number of rows and   binary search in each row will require O(logn) time. That means total complexity will be O(nlogn).
Below is the code:

void binsearch(int **mat, int size, int num)
{
 int low, up, flag,row,mid;
 flag = 0;
 for (row = 0; row < size; row++) {
  low = 0;
  up = size - 1;
  while (low <= up) {
   mid = (low + up) / 2;
   if (mat[row][mid] == num) {
    flag = 1;
    break;
   } else if (mat[row][mid] > num)
    up = mid - 1;
   else
    low = mid + 1;
  }
  if (flag == 1)
   break;
 }
 if (!flag)
  printf("Data not found in the matrix!!!\n");
 else
  printf("Data found at position :%d,%d\n", row + 1, mid + 1);
} 

Third Method:
 In this approach we need some observation on the input. Matrix is sorted in row and column wise. If we look the matrix from the left lower corner then we will find an binary search tree like pattern. Now binary search tree patterns means what? It means in all lesser values are on the leftmost branch of a element and higher values are on the right branch. Obviously it will not be a tree as vertices can be reached by different paths.
Ok lets have an example:
Our input is :
 

   
       +---+---+---+
       |6  |8  |13 |
       +---+---+---+
       |14 |19 |21 |
       +---+---+---+
       |15 |22 | 23|
       +---+---+---+
    

Now check the matrix from lower left corner i.e from element 15 and search for the binary search pattern (forget the left and right orientation concept of general binary search tree). For better understanding check these diagram:

                                                                       Diagram - 1

Here is the binary search tree like pattern.

                                                                       Diagram - 2

In  Diagram - 1 you can see that from a particular position if you move row wise i.e incrementing or decrementing row number, you will find the numbers are decreasing and column wise numbers are increasing. From 15 if you move row wise you will find 15->14->6 (decreasing) and column wise 15->22->23 (increasing). We will use this property for our use.

Algorithm will be as follows:
1]Start search from lowest and leftmost corner.
2]If search-item is greater than the current element then move one column right and follow the same process.
3]If the search-item is lesser than the current element then move one row upward and follow the same process.
4]Continue the process until you find the search-element or any move that take you out of the boundary of the matrix.

We will check dry-run of two example on the above input matrix:
First lets search-item is 13.
Then search will proceed in this way:
15 > 13 so go to 14 (i.e row wise)
14 > 13 go to 6
6 < 13 go to 8 (i.e column wise)
8 < 13 go to 13 and it is the position of 13.

Now lets have a search-item that is not in the matrix.
Let the search-item be 10.
15 > 10 go to 14
14 > 10 go to 6
6 < 10 go to 8
8 < 10 go to 13
13 > 10 go to position (-1,2) (i.e out of the matrix boundary) so stop here and declare that element is not in the matrix.

Here is the code:

#include < stdio .h >
#include < stdlib .h >

void _2D_binsearch(int **mat, int size, int num);
int main(int argc, char **argv)
{
 int **mat, size, num, i, j;
 size = atoi(argv[1]);
 mat = malloc(sizeof(int *) * size);
 for (i = 0; i < size; i++) {
  mat[i] = malloc(sizeof(int) * size);
 }
 printf("Enter the matrix:");
 for (i = 0; i < size; i++)
  for (j = 0; j < size; j++)
   scanf("%d", &mat[i][j]);
 printf("Enter the number to search:");
 scanf("%d", &num);
        //_2D_linear(mat, size, num);
        //binsearch(mat, size, num);
 _2D_binsearch(mat, size, num);
 return 0;
}

void _2D_binsearch(int **mat, int size, int num)
{
 int posx, posy, flag;
 posx = size - 1;
 posy = 0;
 flag = 0;
 while ((posx >= 0) && (posx < size) && (posy >= 0) && (posy < size)) {
  if (mat[posx][posy] == num) {
   flag = 1;
   break;
  } else if (mat[posx][posy] < num)
   posy++;
  else
   posx--;
 }
 if (!flag)
  printf("Data not found in the matrix!!!\n");
 else
  printf("Data found at position :%d,%d\n", posx + 1, posy + 1);
}