hi, i implemented something i called bin2d, here's the pseudo code :
int binSearch2D(int key, int p, int q)
//here we are using binary search on the first row
if(p == q)
if (a[0][p] == key)
i = 0; j = p;
int mid_row = (p + q) / 2;
if (a[0][mid_row] == key)
i = 0; j = mid_row;
else if(a[0][mid_row] > key)
binSearch2D(key, p, mid_row-1);
// we check out the earlier row elements only, no need to check elements of
the column
else
binSearch2D(key, mid_row+1, q);
// here we are then check the elements of the column using binary search
for(int lower = 0, upper = 3; lower <= upper;)
mid_col = (lower + upper) / 2;
if(a[mid_col][mid_row] == key)
i = mid_col; j = mid_row;
return
else if(a[mid_col][mid_row] < key)
lower = mid_col + 1;
else
upper = mid_col - 1;
Since i am nube, i'd appreciate your +/- feedback
thanks,
Akash
On Sun, Feb 27, 2011 at 3:32 PM, gaurav gupta <[email protected]>wrote:
> A 2D matrix is given which is sorted row-wise and column-wise in ascending
> order. Search a given element in minimum possible time.
>
> like matrix is :
>
> 1 2 3 4
> 6 9 12 15
> 7 13 16 19
> 20 21 22 26
>
> and you have to search for 7.
>
> Please don't provide codes, algorithm or pseudo code will be really great.
>
> --
> Thanks & Regards,
> Gaurav Gupta
>
> "Quality is never an accident. It is always result of intelligent effort" -
> John Ruskin
>
> --
> 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.
