Sorry the last solution wont work.
Here's the correct O(n) soln:
Start from top-right element.
If it is greater than the item, go left.
Else go down.
Keep on doing this until you find the element or can not go left or down
(then the element is not in the array).
void 2dsearch(int i, int j, int item)
{
if (i<0 || j<0 || i>n-1 || j>n-1)
{
printf("Not Found\n");
return;
}
if( a[i][j] == item) printf("Found: %d %d\n", i, j);
elseif( a[i][j] > item) 2dsearch(i, j-1, item);
else 2dsearch(i+1, j, item);
}
Call this function as 2dsearch(0, n-1, item);
Cheers
Nikhil Jindal
Delhi College of Engineering
On Sun, Sep 26, 2010 at 8:06 PM, Nikhil Jindal <fundoon...@yahoo.co.in>wrote:
> Here's an O(n) soln:
>
> Start from the bottom right corner. Move up within the last column until
> you reach an element such that the element before that is less than the
> value being searched and this is greater.
> Now move left and check for the same.
> Move one more left. The value can only be in the present column
> after(below) the element we are on.
>
> At max, 3n moves = O(n).
>
> On Sun, Sep 26, 2010 at 7:34 PM, Nikhil Jindal <fundoon...@yahoo.co.in>wrote:
>
>>
>>
>> On Tue, Sep 21, 2010 at 6:05 PM, saurabh singh <saurabh.n...@gmail.com>wrote:
>>
>>> solution 1:
>>> use concept of quad-tree and do binary search in that tree
>>>
>>> solution 2:
>>> do binary search on major diagonal. ultimately u will narrow down to
>>> search for element in 2 rows. in these two rows again do binary search.
>>>
>>
>> How do you narrow down to two rows? Please explain.
>> By searching on the diagonal, you get two elements such that one is lesser
>> than the number being searched for and the next is greater. let them be i,i,
>> and i+1,i+1.
>>
>> So you remove the array from 0,0 to i,i and from i+1,i+1 to n-1,n-1. But
>> the number could be anywhere in the rest of the array
>>
>>
>>>
>>> any solution will lead you to O(log(n)) time
>>>
>>>
>>> On Tue, Sep 21, 2010 at 5:10 PM, jagadish <jagadish1...@gmail.com>wrote:
>>>
>>>> Hi all,
>>>> Given a 2d array which is sorted row wise and column wise as well,
>>>> find a specific element in it in LESS THAN O(n).
>>>> PS: an O(n) solution would involve skipping a column or a row each
>>>> time from the search and moving accordingly.
>>>> Solution less than O(n) is desirable!
>>>>
>>>> --
>>>> 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.
>>>>
>>>>
>>>
>>>
>>> --
>>> Thanks & Regards,
>>> Saurabh
>>>
>>> --
>>> 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.
>>>
>>
>>
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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.
