Searching in two dimensions

Given 2D array with integers sorted both horizontally and vertically. Devise an efficient algorithm to search for key in the 2D array. What is the complexity ?

Eg.  1 4 7 13
       2 5 9 15
       3 6 10 16

Solution :

Two solutions exists :
(Assume the row is sorted from left to right and column from top to bottom so that the least number is at top-left)

First one is :

1. Start from left-bottom
2. While within boundary
1. If key found print and exit
2. If key is smaller move up else move right

Second one :

1. Let M < N (otherwise interchange the usage below)
2. for each M 1D arrays do binary search in O(log N)

Complexity :

First :

• Time : O(M + N)
• Space : O(1)

Second :

• Time : O(M log N)     M < N
• Space : O(1)

The advantage of second method is seen when M << N where second method degenerates to binary search whereas first method degenerates to sequential search.

Code :

/**
 * M rows
 * N columns
 * (row, col) position of searched key if successful
**/

First method :

bool search_2D(int *input, int M, int N, int key, int *row, int *col){

*row = M-1;
*col = 0;

while(*row > 0 && *col < N){

int current = *(input + N*(*row) + (*col));
if(key == current)

return true;

else if(key < current)

(*row)--;

else

(*col)++;

}

return false;

}

Second method :

bool search_2D(int *input, int M, int N, int key, int *row, int *col){

int increment = 1, total_rows = M, total_cols = N;
if(M > N){

increment = N;
total_rows = N;
total_cols = M;

}

for(*row =0; *row < total_rows; i++){

*col = 0;
if(search_1D(input + *row, total_cols, key, col, increment)){

return true;

}

}

return false;

}

bool search_1D(int *input, int N, int key, int *index, int increment){

int low = 0, high = N-1;

while(low <= high){

*index = (low + high)/2;
int value = *(input + (*index)*(increment));

if(value == key)

return true;

else if (value < key)

low = *index + 1;

else

high = *index - 1;

}

return false;

}