Solution: Two solutions exists :
First one is :
Start from left-bottom
While within boundary
If key found print and exit
If key is smaller move up else move right
Second one :
Let M < N (otherwise interchange the usage below)
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
**/
Method 1:
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;
}
Method 2:
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;
}
|
Posts
