# A Python binary search solution - O(logn)

• It is basically an advanced version of the binary search

``````class Solution:
# @param matrix, a list of lists of integers
# @param target, an integer
# @return a boolean
# 8:21
def searchMatrix(self, matrix, target):
if not matrix or target is None:
return False

rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1

while low <= high:
mid = (low + high) / 2
num = matrix[mid / cols][mid % cols]

if num == target:
return True
elif num < target:
low = mid + 1
else:
high = mid - 1

return False``````

• This is brilliant !!

• Strictly, I think this is O(logmn)

• Another solution. small difference in checking boundary

``````class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False

l, r = 0, len(matrix)*len(matrix[0])

while l<r:
mid = (l+r)//2
i, j = mid//len(matrix[0]), mid%len(matrix[0])
if matrix[i][j]==target:
return True
elif matrix[i][j]>target:
r = mid
else:
l = mid + 1

return False
``````

• This post is deleted!

• gj.And here is my solution, beat 100% and I think it is easy to understand

``````if not matrix or not matrix[0]: return False
for i in range(len(matrix)):
if target==matrix[i][-1]: return True
elif target<matrix[i][-1]:
for j in range(len(matrix[0])):
if matrix[i][j]==target: return True
return False
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.