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.
