if we do not know k, how do we find it? inthe series : 17 15 13 11 9 1 3 5 7
we can take k at element 1 also as the descending series can be 17 15 13 11 9 1 and ascending 3 5 7 OR descending 17 15 13 11 9 and ascending 1 3 5 7 isn't there any relationship in kth and (k+1)th element that helps us find out k correctly On Thu, Aug 4, 2011 at 7:37 AM, Ankur Khurana <[email protected]>wrote: > For question two , > try this. > > see te element at arr[0] . and supose you have to find k . if arr[0]==k , > then yes we found the element else see the diff betweem arr[0] and k. that > will be minimum amount of steps needed to convert a[0] to k(let abs(a[0]-k) > = p). then repeat the procedure again at the new element arr[p] untill you > find the number of reach end of array...... > > > On Thu, Aug 4, 2011 at 6:59 AM, Dave <[email protected]> wrote: > >> @Amit: If k is not known, you can find it with another binary search. >> >> Dave >> >> On Aug 3, 3:02 pm, amit karmakar <[email protected]> wrote: >> > I think for question 1, the value of k is not provided, right? >> > >> > On Aug 4, 12:53 am, Ankur Garg <[email protected]> wrote: >> > >> > >> > >> > > Dave's solution looks gud to me :) >> > >> > > On Wed, Aug 3, 2011 at 3:52 PM, Ankur Garg <[email protected]> >> 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 <[email protected]> >> 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 <[email protected]> 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 [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.- Hide quoted text - >> > >> > - Show quoted text - >> >> -- >> 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. >> >> > > > -- > Ankur Khurana > Computer Science > Netaji Subhas Institute Of Technology > Delhi. > > -- > 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. > -- Tushar Bindal Computer Engineering Delhi College of Engineering Mob: +919818442705 E-Mail : [email protected] Website: www.jugadengg.com -- 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.
