## 题目

(This problem is an **interactive problem**.)

A binary matrix means that all elements are `0`

or `1`

. For each **individual** row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a `1`

in it. If such index doesn’t exist, return `-1`

.

**You can’t access the Binary Matrix directly.** You may only access the matrix using a `BinaryMatrix`

interface:

`BinaryMatrix.get(x, y)`

returns the element of the matrix at index`(x, y)`

(0-indexed).`BinaryMatrix.dimensions()`

returns a list of 2 elements`[n, m]`

, which means the matrix is`n * m`

.

Submissions making more than `1000`

calls to `BinaryMatrix.get`

will be judged *Wrong Answer*. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix `mat`

as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

1 | Input: mat = [[0,0],[1,1]] |

Example 2:

1 | Input: mat = [[0,0],[0,1]] |

Example 3:

1 | Input: mat = [[0,0],[0,0]] |

Example 4:

1 | Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]] |

Constraints:

`1 <= mat.length, mat[i].length <= 100`

`mat[i][j]`

is either`0`

or`1`

.`mat[i]`

is sorted in a non-decreasing way.

## 思路

**Hint #1**

(Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.

**Hint #2**

(Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

其实sorted二维数组的查找都可以通过此方法:

首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；否则每一次都在数组的查找范围中剔除一行或者一列，直到找到要查找的数字，或者查找范围为空。

时间复杂度为O(max(n,m))

## 代码

1 | # """ |