Hi,
I think the following approach will work.
1. As the array is sorted in all three directions, assume the 3D array to
be a stack of rectangular arrays or 2D arrays.
Searching in a 2D array of size M*N is trivial - time complexity O(m +
n). Provided that the 2D array is sorted, both row and column wise
2. Now the problems comes down to which 2D array to search. For this we can
use binary search on the 3d dimension in the following way -
- We know that if an element lies in a sorted 2D array, it value must
lie between the top-left element arr[0][0] and bottom right element
arr[m-1][n-1].
- Perform a binary search to find the probable rectangle (2D array) in
which the given element lies. Let say the 3rd dimension is r. Check for the
r/2th rectangle.
If the top-left element and the bottom-right element of the r/2 2D
array > element, search the lower half in the 3rd dimension.
If the top-left element and the bottom-right element of the r/2 2D
array < element, search the upper half in the 3rd dimension.
If the top-left < element and the bottom-right element > element,
this should be the probable 2D array.
3. Search for the 2D array find in the 2nd step, if element is found -
Search is successful--:) else element doesn't exist
If no such 2D array is present as in the 2nd step, the element doesn't
exist
Worst case complexity for an arr[l][m][n] - O(m+n)*logl
The invariant in this approach is that for a 2D array, all its elements are
>= the previous 2D arrays. So if the minimum element of a 2D array i.e the
top-left
element is smaller than element to be searched, there is no need to search
for the earlier arrays. Similar is the case for greater than case.
On Friday, July 20, 2012 11:24:08 AM UTC+5:30, Sakshi Agrawal wrote:
>
> How will you search an element in sorted 3D Array ? ( Sorted in all the 3
> directions )
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/XSZVSbXF2H8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
