Search a 2D Matrix in C++

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

This problem can be solved by 2 ways.
1. By eliminating one row or column at a time.
2. By binary search.

1. By eliminating one row or column at a time.

We start from top right corner (matrix[0][n-1]) and check if the “target” is greater than matrix[0][n-1] remove the row, else if the “target” is lesser than matrix[0][n-1], then remove the column.

Let us analyze by taking an example:

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3

Pass 1:

m = 0
n = 3

if(target == matrix[0][3]) => false;

if(target > matrix [0][3] ) ? => if (3 > 7) false

if(target < matrix [0][3] ) ? => if (3 < 7) true
remove last column. n –-

Pass 2:

m = 0
n = 2

if(target == matrix[0][2]) => false;

if(target > matrix [0][2] ) ? => if (3 > 5) false

if(target < matrix [0][2] ) ? => if (3 < 5) true
remove last column. n —

Pass 3:

m = 0
n = 1

if(target == matrix[0][1]) => true;

Hence the result is true.

2. By binary search.

If you observe the matrix carefully, it can be treated as a sorted array. Hence we can apply binary search to search the “target”.

Below is the formula we use to convert a matrix to an array and vice-versa.

To convert a matrix into an array => matrix[x][y] => a[x * m + y]
To convert an array into a matrix => a[x] =>matrix[x / m][x % m];

Solution in C++

/*
* File     : search_in_matrix.cpp
*/
#include<iostream>
#include<vector>

using namespace std;
bool search_matrix_eliminating_row_column(vector<vector<int> > &matrix, int target) 
{

	int row_length = matrix.size();
	int column_length = matrix[0].size();

	//edge case
	if (target < matrix[0][0] || target > matrix[row_length - 1][column_length - 1]) return false;

	int row = 0;
	int column = column_length-1;
	while(row >=0 && row < row_length && column >= 0 && column<column_length)
	{
		if(target == matrix[row][column]) return true;

		else if(target > matrix[row][column]) row++;
		else if(target < matrix[row][column]) column--;
	}
	return false;
}


bool search_matrix_binary_search(vector<vector<int> > &matrix, int target) 
{


	int row = matrix.size();
	int column = matrix[0].size();

	//edge case
	if (target < matrix[0][0] || target > matrix[row - 1][column - 1]) return false;

    //get the length for the array.
	int left = 0;
	int right = row * column - 1;

	while (right > left) 
	{
		int mid = left + (right - left) / 2;

		if (matrix[mid/column][mid%column] < target)
		{ 
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}
	return matrix[right/column][right%column] == target;

}


int main()
{

//Initialize 2D vector

	vector<vector<int> > matrix = { { 1, 3, 5, 7 },
                                   { 10, 11, 16, 20 },
                                   { 23, 30, 34, 50 },
                                  };

  	int target = 3;
  	                         
   	//bool result = search_matrix_eliminating_row_column(matrix, target);
   	bool result = search_matrix_binary_search(matrix, target);

   	if(result)
   	{
   		cout<<"The target is present in the matrix"<<endl;
   	}
   	else
   	{
   		cout<<"The target is NOT present in the matrix"<<endl;
   	}

	return 0;

}