# LeetCode 074Search a 2D Matrix

## LeetCode 074 Search a 2D Matrix Problem

``````class Solution(object):
# def searchMatrix(self, matrix, target):
#     """
#     :type matrix: List[List[int]]
#     :type target: int
#     :rtype: bool
#     """
#     try:
#         ls_row, ls_col = len(matrix), len(matrix[0])
#     except:
#         return False
#     begin, end = 0, ls_row - 1
#     while begin <= end:
#         mid = (begin +  end) / 2
#         res = self.search_row(matrix, mid, target)
#         if res == 0:
#             return True
#         elif res < 0:
#             end = mid - 1
#         else:
#             begin = mid + 1
#     return False
#
#
# def search_row(self, matrix, row, target):
#     if target < matrix[row][0]:
#         return -1
#     elif target > matrix[row][-1]:
#         return 1
#     begin, end = 0, len(matrix[row]) - 1
#     while begin <= end:
#         mid = (begin + end) / 2
#         if matrix[row][mid] == target:
#             return 0
#         elif matrix[row][mid] < target:
#             begin = mid + 1
#         else:
#             end = mid - 1
#     return 1

def searchMatrix(self, matrix, target):
# binary search
try:
ls_row, ls_col = len(matrix), len(matrix[0])
except:
return False
if target < matrix[0][0] or target > matrix[-1][-1]:
return False
begin, end = 0, ls_row * ls_col - 1
while begin <= end:
mid = (begin + end) / 2
row, col = mid / ls_col, mid % ls_col
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
end = mid - 1
else:
begin = mid + 1
return False

``````