Question on 12.9(Search in a 2D sorted array)/ log time solution? 1.4.11

#1

I’ve looked at some questions about 12.9 but haven’t seen anyone propose this solution here.
Can this problem be solved by binary search?
We could binary search rows in the first column until the start to end difference is 1 row, then get the index of the starting row and binary search on that row. This would give us worst-case log(n) + log(n), so O( log(n) ) ?
Am I looking at this incorrectly?

Thanks.

0 Likes
#2

Hey Alexey,

It is interesting to see an new idea is proposed for this problem, and I have some question about how it works if all the values in the first column are identical, then your algorithm has no idea which row it should perform the subsequent binary search. At that situation, it probably won’t work.

In the earlier version of EPI, we proved O(m + n) is the worst case lower-bound to solve this problem. So I am pretty sure any algorithm whose time complexity is lower than that won’t work.

Please let me know if you have any other problem.

0 Likes
#3

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:
        return False
    if  c_beg > c_end:
        return False

    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:
        return True
    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)
    else:
        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[0])-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.

0 Likes
#4

Hmm, I think that my issue is that my T(n) is not T((3/4 n) + 1…

but T(n) = T((1/4 n)) + T(1/2 n) + 1
and this is not O(log(n)) at all.

0 Likes