I think you can no better. Consider following algorithm:
Extract the n/3 and 2n/3'th elements from each row.
You have altogether 2n elements. Do a pivot operation
(refer to qsort for details), and by some clever bookkeeping,
you can determine whether your target value is in
the first, middle or the last n/3 elements in each row.
So basically speaking, you pay O(2n) time, but you trim your
size by 1/3. Solving this recursion gives a linear time
search!
I am really proud of myself for solving this