Consider the bottom left elment of the given 2 - D array. if it is less than
the number to be search, ignore the whole column and if greater ignore the
whole row. if it is equal note the array index. repeat the above procedure
till all rows and column are scanned. By doing with complexity less than
O(n), we can search the required number from 2D array.
suppose the matrix is
0 1 3 7
2 4 5 8
6 9 10 11
8 12 13 14
We will start with 8 (bottom left element). it is less than 9. We will
ignore the column 1(0 2 6 8). check rest of the element of the last row.
In the second step start from column two and second last row. compare the
corresponding element of the matrix. follow the same steps till you find the
element you are looking for. this will in less than O(n^2) complexity.
I hope it is clear now.
On Mon, Jul 5, 2010 at 11:50 AM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote:
> @ abv i want less then O(n)
>
>
> On Mon, Jul 5, 2010 at 8:14 PM, mohit ranjan <shoonya.mo...@gmail.com>wrote:
>
>> @ 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<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.
