# Python solution with detailed explanation

• Solution

Search a 2D Matrix https://leetcode.com/problems/search-a-2d-matrix/?tab=Description

O(M + log(N)) Solution

1. Very simple problem. Just apply binary search sequentially in each row. O(M + log(N))
2. Notice the nice syntax:
`if matrix[i][0] <= target <= matrix[i][N-1]:`
``````class Solution(object):
# M + log(N) solution
def bsearch(self, nums, low, high, target):
while low <= high:
mid = low + (high-low)//2
if nums[mid] == target:
return True
elif nums[mid] > target:
high = mid-1
else:
low = mid+1
return False

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])
if N == 0:
return False
for i in range(M):
if matrix[i][0] <= target <= matrix[i][N-1]:
return self.bsearch(matrix[i], 0, N-1, target)
return False
``````

O(log(M)) + O(log(N)) Solution

1. Use binary search to select the right row. Then use binary search to search within a column,
``````class Solution(object):
# O(log(M)) + O(log(N))
def bsearch(self, nums, low, high, target):
while low <= high:
mid = low + int((high-low)/2)
if nums[mid] == target:
return True
elif nums[mid] > target:
high = mid-1
else:
low = mid+1
return False

def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
M,N = len(matrix), len(matrix[0])
low, high = 0, M-1
while low <= high:
mid = low + (high-low)//2
if matrix[mid][0] <= target <= matrix[mid][N-1]:
return self.bsearch(matrix[mid], 0, N-1, target)
elif target > matrix[mid][N-1]:
low = mid+1
elif target < matrix[mid][0]:
high = mid-1
return False
``````

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