Search a sorted matrixHard
Given a sorted
matrixof numbers of size
m x n, and a
targetnumber, write a function that determines if the
targetnumber exists in the
For example, if your function recieves the following 3x3 matrix and target number:
matrix = [[1, 3, 8],[9, 21, 24],[25, 28, 32]]target = 7
Your function should return
Given the same matrix, if the
21, your function should return
Note that every row is sorted. Each row starts with a number that is greater than the last number from the previous row.
Before you look at the solution, try to code it yourself.
Time and Space Complexity
Since we cut the problem in half in each iteration, the time complexity is
There is no additional space required. So the space complexity constant