199. Search a 2D Matrix II

Medium · Binary Search

Write an efficient algorithm to search for a target value in an m × n integer matrix. The matrix has the following properties: integers in each row are sorted in ascending order from left to right, and integers in each column are sorted in ascending order from top to bottom.

Return true if the target is found in the matrix, otherwise return false.

Examples

Example 1
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22]], target = 5
Output: true
Explanation: The target 5 is found at position (1, 1) in the matrix.
Example 2
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22]], target = 13
Output: false
Explanation: The target 13 does not exist in the matrix.

Constraints