Search a 2D Matrix

Question

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. [
  2.     [1, 3, 5, 7],
  3.     [10, 11, 16, 20],
  4.     [23, 30, 34, 50]
  5. ]

Given target = 3, return true.

Challenge

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

题解 - 一次二分搜索 V.S. 两次二分搜索

  • 一次二分搜索 - 由于矩阵按升序排列，因此可将二维矩阵转换为一维问题。对原始的二分搜索进行适当改变即可(求行和列)。时间复杂度为 $$O(log(mn))=O(log(m)+log(n))$$
  • 两次二分搜索 - 先按行再按列进行搜索，即两次二分搜索。时间复杂度相同。

一次二分搜索

Python

  1. class Solution:
  2.     def search_matrix(self, matrix, target):
  3.         # Find the first position of target
  4.         if not matrix or not matrix[0]:
  5.             return False
  6.         m, n = len(matrix), len(matrix[0])
  7.         st, ed = 0, m * n - 1
  9.         while st + 1 < ed:
  10.             mid = (st + ed) / 2
  11.             if matrix[mid / n][mid % n] == target:
  12.                 return True
  13.             elif matrix[mid / n][mid % n] < target:
  14.                 st = mid
  15.             else:
  16.                 ed = mid
  17.         return matrix[st / n][st % n] == target or \
  18.                 matrix[ed / n][ed % n] == target

C++

  1. class Solution {
  2. public:
  3.     bool searchMatrix(vector<vector<int>>& matrix, int target) {
  4.         if (matrix.empty() || matrix[0].empty()) return false;
  6.         int ROW = matrix.size(), COL = matrix[0].size();
  7.         int lb = -1, ub = ROW * COL;
  8.         while (lb + 1 < ub) {
  9.             int mid = lb + (ub - lb) / 2;
  10.             if (matrix[mid / COL][mid % COL] < target) {
  11.                 lb = mid;
  12.             } else {
  13.                 if (matrix[mid / COL][mid % COL] == target) return true;
  14.                 ub = mid;
  15.             }
  16.         }
  17.         return false;
  18.     }
  19. };

Java

lower bound 二分模板。

  1. public class Solution {
  2.     /**
  3.      * @param matrix, a list of lists of integers
  4.      * @param target, an integer
  5.      * @return a boolean, indicate whether matrix contains target
  6.      */
  7.     public boolean searchMatrix(int[][] matrix, int target) {
  8.         if (matrix == null || matrix.length == 0 || matrix[0] == null) {
  9.             return false;
  10.         }
  12.         int ROW = matrix.length, COL = matrix[0].length;
  13.         int lb = -1, ub = ROW * COL;
  14.         while (lb + 1 < ub) {
  15.             int mid = lb + (ub - lb) / 2;
  16.             if (matrix[mid / COL][mid % COL] < target) {
  17.                 lb = mid;
  18.             } else {
  19.                 if (matrix[mid / COL][mid % COL] == target) {
  20.                     return true;
  21.                 }
  22.                 ub = mid;
  23.             }
  24.         }
  26.         return false;
  27.     }
  28. }

源码分析

仍然可以使用经典的二分搜索模板(lower bound)，注意下标的赋值即可。

  1. 首先对输入做异常处理，不仅要考虑到matrix为null，还要考虑到matrix[0]的长度也为0。
  2. 由于 lb 的变化处一定小于 target, 故在 else 中判断。

复杂度分析

二分搜索，O(\log mn).

两次二分法

Python

  1. class Solution:
  2.     def search_matrix(self, matrix, target):
  3.         if not matrix or not matrix[0]:
  4.             return False
  6.         # first pos >= target
  7.         st, ed = 0, len(matrix) - 1
  8.         while st + 1 < ed:
  9.             mid = (st + ed) / 2
  10.             if matrix[mid][-1] == target:
  11.                 st = mid
  12.             elif matrix[mid][-1] < target:
  13.                 st = mid
  14.             else:
  15.                 ed = mid
  16.         if matrix[st][-1] >= target:
  17.             row = matrix[st]
  18.         elif matrix[ed][-1] >= target:
  19.             row = matrix[ed]
  20.         else:
  21.             return False
  23.         # binary search in row
  24.         st, ed = 0, len(row) - 1
  25.         while st + 1 < ed:
  26.             mid = (st + ed) / 2
  27.             if row[mid] == target:
  28.                 return True
  29.             elif row[mid] < target:
  30.                 st = mid
  31.             else:
  32.                 ed = mid
  33.         return row[st] == target or row[ed] == target

源码分析

  1. 先找到first position的行， 这一行的最后一个元素大于等于target
  2. 再在这一行中找target

复杂度分析

二分搜索， O(\log m + \log n)