Same applies for this too. 1 2 3 3 5 6 4 7 8
After bsearch on diagonal you are left with (5,6 and 5,7). Do bsearch on this. On Wed, Nov 25, 2009 at 6:27 PM, Bharath <bharath1...@gmail.com> wrote: > Bsearch on diagonal elimanates all the submatrix under 9. > > You are left with only one column and a row.Do BinarySearch on these lists. > > > On Wed, Nov 25, 2009 at 6:07 PM, chitta koushik < > koushik.infin...@gmail.com> wrote: > >> @Bharath >> >> I dont think BinSrch on diagnol and then on row works. >> Can u explain your algo? chk for this matrix >> >> 1 2 3 4 5 >> 2 9 12 19 24 >> 3 10 14 18 20 >> 8 13 15 20 23 >> 11 14 16 21 24 >> >> Find(8) doesn't give o/p >> >> >> --Koushik C >> >> On Wed, Nov 25, 2009 at 5:18 PM, Arun <arunm...@gmail.com> wrote: >> >>> how about splitting the matrix into 4 squares and considering the >>> rightmost bottom and comparing it to topmost left corner of each square. in >>> every iteration you will eliminate atleast one square. so worst case, you >>> have to repeat this divide and conquer on the three other squares. >>> not good as as binary search though(in the sense of eliminating 2 >>> squares). >>> >>> On Wed, Nov 25, 2009 at 3:12 AM, Aditya Shankar < >>> iitm.adityashan...@gmail.com> wrote: >>> >>>> >>>> >>>> On Wed, Nov 25, 2009 at 2:16 PM, Bharath <bharath1...@gmail.com> wrote: >>>> >>>>> You can actually do it in O(logn) complexity. Binary Search on diagonal >>>>> and then on a row. >>>> >>>> Will that always work? >>>> 1 2 3 >>>> 3 5 6 >>>> 4 7 8 >>>> >>>> Find(6) fails with the usual binary search algorithm. >>>> >>>> >>>>> >>>>> >>>>> On Tue, Nov 24, 2009 at 10:33 PM, chitta koushik < >>>>> koushik.infin...@gmail.com> wrote: >>>>> >>>>>> Start from top right or bottom left corner and move according if the >>>>>> element to be searched is lesser or greater than current. >>>>>> >>>>>> >>>>>> --Koushik C >>>>>> Pablo >>>>>> Picasso<http://www.brainyquote.com/quotes/authors/p/pablo_picasso.html> >>>>>> - "Computers are useless. They can only give you answers." >>>>>> >>>>>> >>>>>> On Tue, Nov 24, 2009 at 7:27 PM, Rohit Saraf < >>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>> >>>>>>> A nice problem that i encountered : >>>>>>> In O(n) search for a value x in a sorted NxN matrix. >>>>>>> Definition of sorted matrix: All rows and all columns are sorted in >>>>>>> ascending order. >>>>>>> >>>>>>> So thought of sharing .. >>>>>>> >>>>>>> >>>>>>> Rohit Saraf >>>>>>> Sophomore >>>>>>> Computer Science and Engineering >>>>>>> IIT Bombay >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> <<Bharath>> >>>>> >>>>> >>>>> -- >>>>> 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. >>>> >>> >>> -- >>> 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. >> > > > > -- > <<Bharath>> > > -- <<Bharath>> -- 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.
