Problem
Search for an element in a matrix. Rows and columns of the matrix are sorted in ascending order.
eg. matrix
[1 14 25 35]
[2 16 28 38]
[5 20 28 40]
[16 22 38 41]
search for 38.
The interviewer was looking for a solution better than O(n+m). He didn't want a solution which starts searching from the left bottom and go to right or above according to the key value to search. That solution has O(n+m) worst complexity, where n is row count and m is column count.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Saddleback Search
Created Data : 28-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
bool FindElem(int* arr, int rows, int cols, int value)
{
int low(0);
int up = cols;
int index(-1);
if(arr[0] > value) return false;
if(arr[rows * cols - 1] < value) return false;
int i = 0;
int j = cols - 1;
while(i >= 0 && i < rows && j >=0 && j < cols){
if(arr[i * cols + j] == value) return true;
else if(arr[i * cols + j] < value) i ++;
else j --;
}
return false;
}
void DoTest(int* arr, int rows, int cols, int value)
{
cout << "Find " << value << " in " << endl;
for(int i = 0; i < rows; ++i){
for(int j = 0; j < cols; ++j){
cout << setw(4) << arr[i * cols + j];
}
cout << endl;
}
if(FindElem(arr, rows, cols, value)){
cout << value << " has been found" << endl;
}
else{
cout << "Nothing is found" << endl;
}
cout << "-----------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[4][4] = {
{1, 14, 25, 35},
{2, 16, 28, 38},
{5, 20, 28, 40},
{16, 22, 38, 41}
};
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), -1);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 1); // top left
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 10);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 14);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 16); // bottom left
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 28);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 35); // top right
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 37);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 38);
DoTest((int *)arr, sizeof(arr)/ sizeof(arr[0]), sizeof(arr[0]) / sizeof(arr[0][0]), 41); // bottom right
return 0;
}
Output
Find -1 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
Nothing is found
-----------------------------
Find 1 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
1 has been found
-----------------------------
Find 10 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
Nothing is found
-----------------------------
Find 14 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
14 has been found
-----------------------------
Find 16 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
16 has been found
-----------------------------
Find 28 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
28 has been found
-----------------------------
Find 35 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
35 has been found
-----------------------------
Find 37 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
Nothing is found
-----------------------------
Find 38 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
38 has been found
-----------------------------
Find 41 in
1 14 25 35
2 16 28 38
5 20 28 40
16 22 38 41
41 has been found
-----------------------------
Press any key to continue . . .