Home Search a 2D Matrix
Post
Cancel

LeetCode #74: Search a 2D Matrix (C/C++).

medium

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;
  }
};
This post is licensed under CC BY 4.0 by the author.

Guess Number Higher or Lower

Search in Rotated Sorted Array