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.
