Detailed solution for the problem can be found at http://www.ihas1337code.com/2010/10/searching-2d-sorted-matrix.html
<http://www.ihas1337code.com/2010/10/searching-2d-sorted-matrix.html>He suggested 3-4 methods and compared they complexity also. If you can write down your algorithm may be I can help you out. are you using quad partition : dividing matrix in 3 sub matrix in which one would be dropped. So every time we are reducing size by 3/4. On Wed, Mar 2, 2011 at 8:57 AM, Akash Mukherjee <[email protected]> wrote: > 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. > -- Thanks & Regards, Gaurav Gupta 7676-999-350 "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.
