@ 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 <[email protected]>wrote:
> @amir ..could you please provide a rough pseudocode for it... :-?
>
>
> On Sun, Jul 4, 2010 at 3:12 AM, Amir hossein Shahriari <
> [email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
