Find element in a row wise and column wise sorted matrix.

Question: Given a matrix that is sorted in row wise and column wise, find a number if present in the most efficient way.

Input: Find if 54 is present in matrix.

4	8	15	16	23
6	9	20	21	44
8	11	24	26	49
9	13	25	27	54
10	17	29	30	66

Output: Present

Method 1(Brute force):-

Here, we use two loops search the element in entire matrix. Its a linear search so its not an efficient way to solve this problem.

//K - the element we need to find
void findElement(int[][] matrix, int K, int rows, int cols)
{
	int i,j;

	for(i=0; i<rows; i++)
	{
		for(j=0; j<cols; j++)
		{
			if(matrix[i][j] == K)
			{
				printf("%d found at index%d,%d", K, i,j);
			}
		}
	}
}

Time Complexity:- O(rows * cols)
Space Complexity:- O(1)

Method 2:- (Using Binary Search)

Since we know that the rows are sorted, what we can do is apply the binary search technique in each of the rows. If the element is present we simply return true.

//K - the element we need to find
void findElement(int[][] matrix, int K, int rows, int cols)
{
	int i,j;

	for(i=0; i<rows; i++)
	{
		// Code for Binary Search
		int low = 0;
		int high = cols-1;
		int mid;

		while(low<=high)
		{
			mid = low + (high-low)/2; //To avoid overflow by (low + high)

			if(matrix[i][mid] == data)
			{
				printf("%d, found at %d, %d",K,i,mid);
				return;
			}
			else
			{
				if(matrix[i][mid] < data)
					low = mid + 1; // search in right half
				else
					high = mid - 1; // search in left half
			}
		}
	}

	printf("NOT FOUND");
}

Time Complexity:- O(rows * (cols * log (cols)))
Space Complexity:- O(1)

Method 3: (The most efficient way)

We will try to utilize the fact that the array is sorted in the row wise and column wise manner. That means for every row, the last element is the largest one and for every column, the last element is again the largest one. That means for any given number, all numbers to the right of it and all numbers to the bottom of it will be greater.
We can start search from the top right corner. First, keep going left until we find the exact number (return true), or until we find a number that is smaller. If we find a number that is smaller, we go downward in the matrix. Then again we move to the left, and so on, until we find the number, or hit the boundary of the matrix.

Summary

• Start your search with top right element of given matrix
• Loop: compare this element with K and do the following
  i) If current value is equal to K return its position
  ii) If current element < K then move downward and search the element in next row (if out of bound of matrix then break return false)
  iii) If current element > K then move to the left (if out of bound of matrix then break return false)
• repeat the 2nd step till you find element or returned false

//K - the element to be found
void findElement(int matrix[][], int K, int rows, int cols)
{
	int i = 0, j = cols-1;  //set indexes for top right element

	while (i < n && j >= 0)
	{
		if (mat[i][j] == x)
		{
			printf("\n Found at %d, %d", i, j);
			return;
		}

		if (mat[i][j] > x)
		{
			// We move to the previous column if the element in matrix is larger
			j--;
		}
		else //  if mat[i][j] < x
		{
			// We move to the next row, if the element is smaller
			i++;
		}
	}

	//If we reach here, that means that the element was not found
	printf("\n Element not found");
	return;
}

Time Complexity:- O(rows + cols)
Space Complexity:- O(1)