## 240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

``````[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
``````

Given target = `5`, return `true`.

Given target = `20`, return `false`.

Thoughts:

1. O(mlogn) : iteratively search each row using binary search
2. O(m + n): start at the top right corner. If current number is smaller than target, increase the row number, if it is larger than the target number, decrease the column number, otherwise return False.

Code O(mlogn):

``````class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
def bins(v, target):
low, high = 0, len(v) - 1
while(low <= high):
mid = low + (high - low)/2
if v[mid] > target:
high = mid - 1
elif v[mid] < target:
low = mid + 1
else:
return True
return False

m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
for i in range(m):
if bins(matrix[i], target):
return True
return False
``````

Code O(m + n):

``````class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
row , col = 0, n - 1 # top right
while row < m and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
row = row + 1
else:
# matrix[row][col] > target:
col = col - 1
return False
``````