524. Search a 2D Matrix

Given an m x n matrix where each row is sorted ascending and the first element of every row is greater than the last element of the previous row, determine whether a target value exists. Treat the matrix as a single sorted sequence and binary search it. The input is JSON {matrix, target}. Return true or false.

Input: JSON {matrix, target}.

Output: Boolean — true or false.

Examples

Input: {"matrix":[[1,3,5,7],[10,11,16,20],[23,30,34,60]],"target":3}
Output: true
Explanation: 3 is present.

Input: {"matrix":[[1,3,5,7],[10,11,16,20],[23,30,34,60]],"target":13}
Output: false
Explanation: 13 is absent.

Input: {"matrix":[[1]],"target":1}
Output: true
Explanation: Single cell matches.

Constraints

• 1<=m,n<=100
• matrix fully sorted as described

Asked by