@Shobhit: Can you give me a few hints on implementing a BS on the 2D?
@neelpulse: That's what I said. A 2D array *might* be a probable candidate.
In your example, the first 2d satisfies the criteria...so we check it --
Not found -- Reject -- Move on to next probable candidate.
On Sat, Jul 21, 2012 at 5:14 PM, neelpulse(Jadavpur University) <
neelpu...@gmail.com> wrote:
> May be I am missing a few details. But Consider this 3D array:
> {
> {
> {1,2},
> {7,8} // First 2D array
> },
> {
> {3,4},
> {9,10}
> }
> }
> If you search for 3 then your search in first step will give first 2D
> which actually does not contain 3. As per my interpretation of the problem,
> my array is holding the preconditions.
>
> On Friday, 20 July 2012 16:25:49 UTC+5:30, algo bard wrote:
>>
>> Compare the element with the first([0][0]) and the last
>> element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be
>> present in.
>> After that you can follow this approach : http://www.geeksforgeeks.org/*
>> *archives/11337 <http://www.geeksforgeeks.org/archives/11337>
>>
>> If it's not present in that 2D, move on and search for the next target 2D.
>>
>> The Probable 2D target set will be given by :
>> arr[i][0][0]<=element<=arr[i][**n-1][n-1].
>> Reject the 2Ds which don't follow this condition.
>>
>> TC: O(n^2)
>>
>> Though, I think an O(n) approach must exist for this problem.
>>
>> On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal <sweetsaksh...@gmail.com
>> > 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 post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>> googlegroups.com <algogeeks%2bunsubscr...@googlegroups.com>.
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>
>>
>> --
> 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/-/UKYO8gE0s08J.
>
> 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.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
