@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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [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. > > -- > **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 [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.
