@Dave ..for question 1 why use binary search for 1to k initially say array is
17 15 13 11 9 1 3 5 7 the kth element is 9 ..Now if u want to find 3 why to search in first half ..Just compare with kth element and if greater find on left else go to right :) Not totally conviced with ur solution for 1 st question though it will give answer but not optimized one :) On Wed, Aug 3, 2011 at 4:02 PM, amit karmakar <amit.codenam...@gmail.com>wrote: > I think for question 1, the value of k is not provided, right? > > On Aug 4, 12:53 am, Ankur Garg <ankurga...@gmail.com> wrote: > > Dave's solution looks gud to me :) > > > > > > > > On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg <ankurga...@gmail.com> wrote: > > > Q1 can be looked as rotated sorted array...check whether the no is less > or > > > greater than kth element ..if greater search using binary search with > low =0 > > > high k-1 and if less earch in right with low=k+1 high =n; > > > > > q2) Dont know :( > > > > > On Wed, Aug 3, 2011 at 3:44 PM, Dave <dave_and_da...@juno.com> wrote: > > > > >> @Tushar: For problem 1, do a binary search on elements 1 to k, and if > > >> no hit is found, do a binary search on elements k+1 to n. > > > > >> For problem 2, suppose that you are searching the given array for the > > >> number 2. The idea is to take big steps when you are far from the > > >> target, and small steps when you are close. Start with i = 0. If a[i] > ! > > >> = 2, then add abs(a[i]-2) to i and try again. This is because it will > > >> take at least abs(a[i]-2) steps to get to 2. > > > > >> In this case, i = 0 and a[0] = 6, so add 4 to i, getting 4. a[4] = 4, > > >> so add 2 to i, getting 6. a[6] = 3, so add 1. a[7] = 2. > > > > >> Dave > > > > >> On Aug 3, 2:09 pm, TUSHAR <tusharkanta.r...@gmail.com> wrote: > > >> > 1. Given an array of n-elements ? the 1st k -elements are in > > >> > descending order and k+1 to n elements are in > > >> > ascending order. give an efficient algo for searching an > > >> > element ? > > > > >> > 2. Given an array of n-elements ? each element in the array is > either > > >> > same or less by 1 or larger by 1 from the > > >> > previous element . give an efficient algo for searching an > > >> > element ? > > > > >> > e.g : 6 6 6 5 4 4 3 2 3 4 3 4 ............ > > > > >> -- > > >> 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. > > -- 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.
