let's start from top right element(call p)
if(x<p) then search left else go down ..
complexity is O(n+n).
i=0; j=n-1;
while(i<n && j>=0)
{ if(arr[i][j]==x)
return 1;//found
else if(a[i][j]<x)
i++;
else
j--;
}
return -1;//not found
On Mon, Jul 18, 2011 at 11:30 PM, sivaviknesh s <[email protected]>wrote:
>
>
> ---------- Forwarded message ----------
> From: sivaviknesh s <[email protected]>
> Date: Mon, Jul 18, 2011 at 11:29 PM
> Subject: Fwd: MICROSOFT INTERNSHIP (Coding round)
> To: [email protected]
>
>
>
>
> ---------- Forwarded message ----------
> From: subramania jeeva <[email protected]>
> Date: Thu, Sep 23, 2010 at 7:53 AM
> Subject: Re: MICROSOFT INTERNSHIP (Coding round)
> To: [email protected]
>
>
> Also in placement the question asked was
>
> Given a 2 dimensional matrix with its rows and columns are
> in sorted order. You've to find a number and return its positions from that
> matrix... I think the efficient way is binary search... It'll take log(n^2)
> to the base 4.
>
> Mostly they're expecting C code rather than C++.... So
> improve your C knowledge..
>
>
>
> say........
>
> 1 2 3
> 4 5 6
> 7 8 9
>
> ...say u ve to find '8'....
>
> start from 1 ...check its right (2) nd down (4)
>
> 4>2 (but 4<8)....so go to 4....again check its right (5) nd down (7)
>
> 7>5....finally reached 8 in four steps....complexity is less than o(m*n)...
>
> ...am i rite???
>
>
>
>
>
>
>
>
> Cheers
> ~ Jeeva ~
>
>
>
> --
> Regards,
> $iva
>
>
>
>
> --
> Regards,
> $iva
>
> --
> 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.
>
--
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.
