@ Jalaj
suppose the matrix is
0 1 3 7
2 4 5 8
6 9 10 11
8 12 13 14
element to search=9;
start at right-top element i.e curr_elem=7
9>curr_elem, move down
curr_elem=8
9>curr_elem, move down
curr_elem=11
9<curr_elem, move left
curr_elem=10
9<curr_elem, move left
you reach 9, in O(n) time...
hope is't clear now :)
Mohit
On Sun, Jul 4, 2010 at 3:13 PM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote:
> @amir ..could you please provide a rough pseudocode for it... :-?
>
>
> On Sun, Jul 4, 2010 at 3:12 AM, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com> wrote:
>
>> @jalaj: oops! i'm sorry but by diameter i meant diagonal!
>>
>> binary search on the diagonal 0 4 10 14 the result is 4<9<10
>> so the matrix that ends with 4:
>> 0 1
>> 2 4
>> and the matrix that starts with 10:
>> 10 11
>> 13 14
>> can't have 9 in them
>> so we continue the search in
>> 3 7
>> 5 8
>> and
>> 6 9
>> 8 12
>>
>> applying the search on
>> 3 7
>> 5 8
>> we see that 8<9 which is the biggest element of the matrix
>> so this can't have 9 in it
>> and the search in
>> 6 9
>> 8 12
>> yields that 6<9<12
>> so the result would be in 8 or 9
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
