@Saurabh: Here's a challenge for you. Suppose I give you an array of length 1024 with the first 987 elements in sorted order and the remaining elements unsorted. Knowing that you can probe any of the 1024 elements, without making explicit use of the fact that you know that 987 elements are sorted, design an O(log n) search that will locate any one of the first 987 elements. If you can do that, then the answer to your question is "Yes."
Dave On Aug 20, 9:51 pm, saurabh singh <saurab...@gmail.com> wrote: > @dave may be its a bit offtopic,(and may be stupid) but if the numbers are > in a small range (say 1 to 1000) isn't the probability that the absolute > garbage value would be greater than the array elements(assuming garbage to > be bits of random 0's and 1's)?Assuming we have not entered into some other > valid memory area.Can't this fact be used to produce a solution that's valid > for most of the cases? > > On Sat, Aug 20, 2011 at 12:21 AM, sagar pareek <sagarpar...@gmail.com>wrote: > > > > > > > thanks for pointing it out > > > On Sat, Aug 20, 2011 at 12:16 AM, Dave <dave_and_da...@juno.com> wrote: > > >> @Sagar: So far so good, but you are not guaranteed to get an > >> exception. Example, int a[987] is followed in memory by char > >> b[10000000], which is a dictionary. You won't detect an exception > >> until you get to at least a[262144] (2 to the 18th). But you will pick > >> up plenty of garbage which may throw off your binary search. > > >> Dave > > >> On Aug 19, 1:26 pm, sagar pareek <sagarpar...@gmail.com> wrote: > >> > Well > >> > sorry but i forget to mention exceptions in the solution. > >> > Here is the complete solution :- > > >> > The key idea here is to simultaneously do a binary search > >> > for the end of the array as well as the key. We try to look for A[2k ] > >> in > >> > the > >> > k-th step and catch exceptions for successive values of k till either we > >> hit > >> > an exception or we hit a number greater than or equal to b. Then we do > >> > a binary search for b between indices 2k - 1 and 2k . The runtime of the > >> > search algorithm is 0 (l og 叫. > > >> > On Fri, Aug 19, 2011 at 11:53 PM, Dave <dave_and_da...@juno.com> wrote: > >> > > @Everyone: The problem says that the array is of UNKNOWN length, but > >> > > all of the solutions presented assume that the array is of INFINITE > >> > > length. Suppose, e.g., that the length is 987, but you don't know > >> > > that. Then it will be meaningless to probe at 1, 10, 100, 1000, etc, > >> > > or 1, 2, 4, ..., 512, 1024 because any probe beyond 987 is outside the > >> > > array. An address violation may occur, or arbitrary data, unrelated to > >> > > the data in the array may be used. I think the problem as stated is > >> > > unsolvable. > > >> > > Dave > > >> > > On Aug 19, 12:48 pm, sagar pareek <sagarpar...@gmail.com> wrote: > >> > > > HI, > > >> > > > I have encountered a problem :- > > >> > > > You have an array of *UNKNOWN *length . And you have to find an > >> element > >> > > > in O(log(n)) time without using any extra space. > > >> > > > -- > >> > > > **Regards > >> > > > SAGAR PAREEK > >> > > > COMPUTER SCIENCE AND ENGINEERING > >> > > > NIT ALLAHABAD > > >> > > -- > >> > > 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 > >> > SAGAR PAREEK > >> > COMPUTER SCIENCE AND ENGINEERING > >> > NIT ALLAHABAD > > >> -- > >> 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 > > SAGAR PAREEK > > COMPUTER SCIENCE AND ENGINEERING > > NIT ALLAHABAD > > > -- > > 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. > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD- 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 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.
