Problem 2 can be solved in O(n/k). If you want to search for x, look at the first element. If the element is not found, find the difference between the current element and x, let this be stored in diff. Now, x will be atleast diff number of positions ahead in the array. So, the next position is current position + diff. If the element is still not found, continue.
On Thu, Aug 4, 2011 at 5:27 PM, Dave <[email protected]> wrote: > @Amit: It is given that the array is decreasing, then increasing. An > array of constants is neither increasing nor decreasing. > > Dave > > On Aug 3, 11:41 pm, amit karmakar <[email protected]> wrote: >> Can you show how to find k for an array containing n 2's using binary >> search. >> >> On Aug 4, 6:29 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.-Hidequoted text - >> >> > > - Show quoted text -- 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. > > -- Gaurav Menghani -- 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.
