Re: [algogeeks] Re: m*n matrix, sorted rows, sorted columns, WAP to find an element efficiently
we can also apply binary search on rows and columns separately by which we will decide that in which 1/4th part we need to search.So in this case complexity will be O(log m + log n). just check and let me know... On Wed, Apr 4, 2012 at 5:27 AM, Ashish Goel wrote: > why not start from middle(m/2, n/2) > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Wed, Apr 4, 2012 at 12:29 AM, Karthikeyan V.B wrote: > >> Hi, >> >> Start from right top corner >> If matrix element > key move to previous column >> else if matrix element < key move to next row >> >> int search(int** a,int key,int m,int n) >> { >> if (key < a[0][0] || key > a[m-1][n-1]) return 0; >> int min=a[0][n-1],i=0,j=n-1; >> while(i<=m-1 && j>=0) >> { >> if(a[i][j] > key) >> j--; >> else if(a[i][j] < key) >> i++; >> else >> return 1; >> } >> return 0; >> } >> >> Regards, >> Karthikeyan.V.B >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- Regards Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@gmail.com -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: m*n matrix, sorted rows, sorted columns, WAP to find an element efficiently
why not start from middle(m/2, n/2) Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Apr 4, 2012 at 12:29 AM, Karthikeyan V.B wrote: > Hi, > > Start from right top corner > If matrix element > key move to previous column > else if matrix element < key move to next row > > int search(int** a,int key,int m,int n) > { > if (key < a[0][0] || key > a[m-1][n-1]) return 0; > int min=a[0][n-1],i=0,j=n-1; > while(i<=m-1 && j>=0) > { > if(a[i][j] > key) > j--; > else if(a[i][j] < key) > i++; > else > return 1; > } > return 0; > } > > Regards, > Karthikeyan.V.B > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: m*n matrix, sorted rows, sorted columns, WAP to find an element efficiently
Hi, Start from right top corner If matrix element > key move to previous column else if matrix element < key move to next row int search(int** a,int key,int m,int n) { if (key < a[0][0] || key > a[m-1][n-1]) return 0; int min=a[0][n-1],i=0,j=n-1; while(i<=m-1 && j>=0) { if(a[i][j] > key) j--; else if(a[i][j] < key) i++; else return 1; } return 0; } Regards, Karthikeyan.V.B -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
[algogeeks] Re: m*n matrix, sorted rows, sorted columns, WAP to find an element efficiently
This search can be done easily in O(n+m) start from top right corner. chek out this link you will understand!! http://www.geeksforgeeks.org/archives/11337 On Sunday, 1 April 2012 21:18:26 UTC+5:30, ashgoel wrote: > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/bK0lXBQtrSEJ. To post to this group, send email to algogeeks@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.