In sorted array, we can search in O(logn) by binary search. But I thought that in n*n array, how can we apply this algorithm(or other) to the array to search faster? n*n list is sorted each row and column like below.
1 3 7 13 19
2 5 12 14 20
4 9 15 16 22
8 10 18 23 25
11 17 21 24 27
Obviously the naive solution is to perform binary search on each row (or column) which will result in a runtime complexity of O (n log n).
The main problem I see in directly adapting binary search to the whole matrix is that there is no complete ordering. This makes it hard to define a "split element" where all elements to the "left" are smaller and all elements to the "right" are larger.
My approach for a direct adaptation would be closer to a spatial index like a quad-tree. The basic observation is the following: For each sub-matrix of the original matrix you can define bounds of the elements by looking at the top-left (lower bound) and bottom-right (upper-bound) element.
Now you can basically perform depth first search, recursively splitting the matrix in 4 sub matrices, computing upper and lower bounds for each sub matrix and discarding or exploring it depending if the key is within its bounds.
