Searching a 2D sorted matrix

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j].

C++:
01 bool twoDsearch(vector <int*> A,int  r,int c,int key,int& row,int& col)
02 {
03     int p=r1;
04     int q=0;
05     while((p>=0)&&(q<c)){
06         if(A[p][q]==key){
07             row=p;
08             col=q;
09             return true;
10         }
11         if(A[p][q]<key)
12             q++;
13         else
14             p;
15     }
16     return false;
17 }
Advertisements
This entry was posted in Divide and Conquer. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s