Hi, when doing this exercise I end up with a simple recursive approach that remove 3/4 of the table at each step. Here is my code:
def matrix_search(A, x):
def helper(r_beg, r_end, c_beg, c_end):
if r_beg > r_end:
if c_beg > c_end:
r_mid = r_beg + (r_end-r_beg)//2
c_mid = c_beg + (c_end-c_beg)//2
mid = A[r_mid][c_mid]
if mid == x:
if mid > x:
return helper(r_beg, r_mid-1, c_beg, c_end) or helper(r_mid, r_end, c_beg, c_mid-1)
return helper(r_mid+1, r_end, c_beg, c_end) or helper(r_beg, r_mid, c_mid+1, c_end)
return helper(0, len(A)-1, 0, len(A)-1)
In my understanding it seems to be quite close to bin search for 2D.
Here is the complexity analysis (I am quite sure I am wrong somewhere, if you could help me to spot the issue):
n = number of entries in the array
T(n) = T((3/4) n) + 1
Thus: T(n) = a * T(n/b) + O(n**d) with a = 1, b = 4/3, d=0,
-> using master theorem -> time complexity: O(n^d log(n)) = O(log(n))
space_complexity: recursive call_stack = O(log(n))
What do you think ?
I run the judge on it, I got: Average running time: 11us, median running time: 7us, all test passed. With the code from the python book I got Average running time: 6us, median running time: 4us. That’s why I think I have done a mistake in my complexity analysis, because it should be faster and it’s not.
Thanks in advance.