source: https://leetcode.com/problems/search-a-2d-matrix
C/C++ Solution to LeetCode problem 74. Search a 2D Matrix.
Problem
You are given an m x n
integer matrix matrix
with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target
, return true
if target
is in matrix
or false
otherwise.
You must write a solution in O(log(m * n))
time complexity.
Examples
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Solution
Two binary searchs (nested or not). First, we find the row where the number should be located. Then, with a second binary search we find the position of the number.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool inRow = false;
int l = 0;
int h = matrix.size() - 1;
int m;
while (l<=h) {
m = (l + h) / 2;
if (matrix[m][0] == target || matrix[m][matrix[m].size() - 1] == target)
return true;
if (matrix[m][0] < target && matrix[m][matrix[m].size() - 1] > target) {
inRow = true;
break;
}
if (matrix[m][0] > target)
h = m - 1;
if (matrix[m][matrix[m].size() - 1] < target)
l = m + 1;
}
if (inRow) {
l = 0;
h = matrix[m].size() - 1;
int m2;
while (l <= h) {
m2 = (l + h) / 2;
if (matrix[m][m2] == target)
return true;
if (matrix[m][m2] > target)
h = m2 - 1;
if (matrix[m][m2] < target)
l = m2 + 1;
}
}
return false;
}
};