Binary Search in 2D Arrays | Dataford Interview Questions

How would you solve binary search in a 2D array II style problem?

Implement search_matrix(matrix, target) to return True if target appears in a non-empty matrix whose rows and columns are sorted in nondecreasing order, otherwise return False. Use an efficient search strategy with constant auxiliary space.

Constraints

1 <= len(matrix) <= 500
1 <= len(matrix[0]) <= 500
All rows have the same length
-10^9 <= matrix[row][col], target <= 10^9
Each row and each column is sorted in nondecreasing order

Function Signature

def search_matrix(matrix, target):

Your question is Binary Search in 2D Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

How would you solve binary search in a 2D array II style problem?

Constraints

1 <= len(matrix) <= 500
1 <= len(matrix[0]) <= 500
All rows have the same length
-10^9 <= matrix[row][col], target <= 10^9
Each row and each column is sorted in nondecreasing order

Function Signature

def search_matrix(matrix, target):

Your question is Binary Search in 2D Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.