Search a 2D Matrix

Medium

binary-searchmatrix

You are given an r × c matrix where each row is sorted ascending and the first value of each row is greater than the last value of the previous row. Determine whether target exists in the matrix, in O(log(r·c)).

Input

Line 1: two integers r c
Next r lines: the matrix rows
Last line: the integer target

Output: true or false.

Example 1

Input:

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

Output:

true

Example 2

Input:

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

Output:

false

Constraints

1 ≤ r, c ≤ 100
Rows sorted; row starts exceed previous row ends.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Search a 2D Matrix

Medium

binary-searchmatrix

Input

Line 1: two integers r c
Next r lines: the matrix rows
Last line: the integer target

Output: true or false.

Example 1

Input:

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

Output:

true

Example 2

Input:

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

Output:

false

Constraints

1 ≤ r, c ≤ 100
Rows sorted; row starts exceed previous row ends.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.