search a 2d matrix

search a 2d matrix

Easy problem

Binary search the rows and then binary search the columns.

 1 class Solution {
 2 public:
 3     bool searchMatrix(vector<vector<int> > &matrix, int target) {
 4         int n = matrix.size();
 5         if ( !n ) {
 6             return false;
 7         }
 8         int m = matrix[0].size();
 9         if ( !m ) {
10             return false;
11         }
12         int l = 0;
13         int r = n-1;
14         int  mid = 0;
15         while ( l <= r ) {
16             mid = l+(r-l)/2;
17             if ( matrix[mid][0] <= target && target <= matrix[mid][m-1] ) {
18                 break;
19             }
20             if ( matrix[mid][0] >= target ) {
21                 r = mid-1;
22             }
23             if ( matrix[mid][m-1] <= target ) {
24                 l = mid+1;
25             }
26         }
27         if ( l > r ) {
28             return false;
29         }
30         int t = mid;
31         l = 0;
32         r = m-1;
33         while ( l <= r ) {
34             mid = l + (r-l)/2;
35             if ( matrix[t][mid] == target ) {
36                 return true;
37             }
38             if ( matrix[t][mid] < target ) {
39                 l = mid+1;
40             }
41             if ( matrix[t][mid] > target ) {
42                 r = mid-1;
43             }
44         }
45         return false;
46     }
47 };

Loading Disqus comments...
Table of Contents