Search a 2D Matrix

Question

• leetcode: Search a 2D Matrix | LeetCode OJ
• lintcode: (28) Search a 2D Matrix

Problem Statement

Write an efficient algorithm that searches for a value in an _m_ x _n_ matrix.

This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example

Consider the following matrix:

[
 [1, 3, 5, 7],
 [10, 11, 16, 20],
 [23, 30, 34, 50]
]

Given target = 3, return true.

Challenge

O(log(n) + log(m)) time

Problem solution-one binary search VS two binary search

• One binary search -Since the matrices are arranged in ascending order, a two-dimensional matrix can be converted into a one-dimensional problem. Make appropriate changes to the original binary search (find rows and columns). The time complexity is $$O(log(mn))=O(log(m)+log(n))$$
• Two binary searches-press line first Then search by column, that is, two binary searches. The time complexity is the same.

One ​​binary search

Python

1
2
 3
4
5
6
7
8
9
10
11
12
13
14
 15
16
17
18< /span>

class Solution:
 def < span class="hljs-title">search_matrix(self, matrix, target):
 # Find the first position of target
 if not matrix or not span> matrix[0]:
 return False
 m, n = len(matrix), len(matrix[0])
 st, ed = 0, m * n- 1

 while st + 1 
 m id = (st + ed) / 2
 if< /span> matrix[mid / n][mid% n] == target:
 return True
 elif matrix[mid / n][ mid% n] 
 st = mid
  else:
 ed = mid
 return  matrix[st / n][st% n] == target or 
 matrix[ ed / n][ed% n] == target

C++

1
2
3
4
5
6
7
8
9
 10
11
12
13< /span>
14
15
16
17
18
19< br>

class  Solution {
public :
 bool searchMatrix(vector<vector<int>>& matrix, int target) {
 if (matrix.empty() || matrix[0].empty()) return false;

 int ROW = matrix.size(), COL = matrix[0].size( );
 int lb = -1 , ub = ROW * COL;
 while (lb +  1 
 int mid = lb + (ub-lb) / < span class="hljs-number"> 2;
 if (matrix[mid / COL][mid% COL] 
 lb = mid;
} else
} else span> {
 if (matrix[mid / COL][mid% COL] == target) < span class="hljs-keyword">return true;
 ub = mid;< /span>
 }
 }
 return false;
 }
 };

Java

The lower bound binary template.

1 
2
3
4
5
6
7
< span class="line">8
9
10
11
12
13
14
15
16
17
18
19
20 
21
22
23
24
25
26 
27
28

public class Solution {
 /**
 * @param< /span> matrix, a list of lists of integers
 * @param target, an integer
 * @return a boolean, indicate whether matrix contains target
 */ 
 public  boolean searchMatrix(int[][] matrix, int target) {
 if (matrix == null || matrix.length == 0 || matrix[0] == null) { 
 return false; 
 }

 int ROW = matrix.length, COL = matrix[0].length;
 int lb = -1, ub = ROW * COL;
 while (lb + 1 
  int mid = lb + (ub-lb) / 2;
 if (matrix[mid / COL][mid% COL] 
 lb = mid;
} else {
 if (matrix[mid / COL][mid% COL] == target) {
 return true;
 }
 ub = mid;
 }
 }

 return false;
 }
}

Source code analysis

The classic binary search template (lower bound) can still be used, just pay attention to the subscript assignment.

1. First, do exception handling for the input, not only taking into account that matrix is ​​null, but also that the length of matrix[0] is also 0.
2. Because the change of lb must be smaller than target, it is judged in else.

Complexity analysis

Binary search, $$O(log mn)$$.

twice dichotomy

Python

1
2
3 
4
5
6
7
8
9 
10
11
12
13
14
15
< span class="line">16
17
18
19
20
21
22
23
24
25
26
27
28 
29
30
31
32
33

Source code analysis

1. First find the line of first position, and the last element of this line is greater than or equal to target
2. Find target in this line

complexity analysis

Binary search, $$O(log m + log n)$ $

Original: Large Column Search a 2D Matrix