# Binary search in diagonal element! O(log^2 n*m)maybe? Share my thinking process..

• Well, as the problem states,think of an 2x2 matrix,
[
a, b;
c, d;
]
we can clearly know that a is the min number and d is the max number,
the we put this 2x2 matrix into a big matrix:

``````............... ....................
.....Z1........ .........Z2.........
...............  ...................
..............a b...................
..............c d...................
......Z3....... .........Z4.........
................ ...................
``````
• If the target is >a and <d, we can discard elements in Z1 and Z4!
(since all elements in Z4 is bigger than d && all elements in Z1 is
smaller than Z1).
• Then we redo the process in Z2 and Z3.

So,how to find a and d?Because the diagonal elements is ordered, we just simply binary search in the diagonal elements and find the lower bound of our target.

Suppose N=n*m;
we get T(N)=2T(N/2)+O(lgN)
T(N)=O(lg^2N)?

• That's one of the rarer approaches, but no, it's neither new nor O(lg^2N). Your T(N)=T(N/2)+O(lgN) is wrong in two ways:

• You have *two* subproblems and can't just pretend they're only one.
• If the abcd-block is in a corner of the matrix, then the larger subproblem can be far larger than N/2. Almost N.

• yeah, I found it later... the size of my subproblem is not sure.... But I wonder how to calculate the time complexity of this approache? Thanks for your comment any way~

• Your new version, the T(N)=2T(N/2)+O(lgN), results in Θ(N), not O(lg^2N).

Not sure why you say N/2, though. It's still invalid, and if you mean the two subproblems being equally large, it should be N/4. And T(N)=2T(N/4)+O(lgN) leads to Θ(sqrt(N)).

Not sure how to analyze it properly and I don't really want to, but maybe 1337c0d3r's article can help.

• Thank you! the article really helps me.

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