Search a 2D Matrix

medium

You are given an m x n integer 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 the matrix, or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Test Cases

Copy an input into the main harness and Run to verify

Input

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

Expected Output

true

Input

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

Expected Output

false

Hint 1 — click to reveal

Those two properties together mean the matrix is one sorted array that has been wrapped into rows.

Hint 2 — click to reveal

Treat index i as row i / n and column i % n.

Java Compiler