Given a 2D matrix that contains integers only, which each row is sorted in an ascending order. The first element of next row is larger than (or equal to) the last element of previous row.
Given a target number, returning the position that the target locates within the matrix. If the target number does not exist in the matrix, return {-1, -1}.
Assumptions:
The given matrix is not null, and has size of N * M, where N >= 0 and M >= 0.
Examples:
matrix = { {1, 2, 3}, {4, 5, 7}, {8, 9, 10} }
target = 7, return {1, 2}
target = 6, return {-1, -1} to represent the target number does not exist in the matrix.
class Solution(object):
def search(self, matrix, target):
n = len(matrix)
m = len(matrix[0])
left = 0
right = m*n - 1
res = [-1,-1]
while left <= right :
mid = (left + right)/2
rowindex = mid/m
colindex = mid%m
if matrix[rowindex][colindex] == target:
res[0] = rowindex
res[1] = colindex
return res
elif matrix[rowindex][colindex] < target:
left = mid + 1
else: right = mid - 1
return res
