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] == target || matrix[m][matrix[m].size() - 1] == target) return true; if (matrix[m] < target && matrix[m][matrix[m].size() - 1] > target) { inRow = true; break; } if (matrix[m] > 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; } };