# Python Binary Search Beats 100%, very simple explaination.

• All we're doing is binary search, but transforming our index we use in a 1D array into that of the indices of the 2D array.
If we have a 3 by 4 2D array as such:
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
We easily see that this is equivalent to laying these out in a single array:
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)
The column will always be 0, 1, 2, or 3 and the overflow will become the row. So if we have index 4 in the 1D array(so the 5th element), we have (4/4, 4%4) = (1, 0).

``````def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0:
return False
left = 0
right = len(matrix) * len(matrix[0]) - 1
column = len(matrix[0])
while left <= right:
mid = (right + left)/2
i = mid / column
j = mid % column
if (matrix[i][j] == target):
return True
elif (matrix[i][j] < target):
left = mid + 1
else:
right = mid - 1
return False
``````

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