We can use the following stategy: We consider range = 1 and search for given X among those 1 nos, if not found i.e. if X>a[range-1] , we increase range = range*2. If such right end is found , where a[range-1] > X, then we are sure that X is somewhere b/w index [0, range-1] ..... And now do simple binary search. So, complexity = finding the apt. right end. + finding X = log n + log n = log n
Shruti On Sep 30, 10:52 pm, Adi Srikanth <adisriika...@gmail.com> wrote: > if its an array, you can get the size of an array from sizeof(array) divided > by size of element type....then we can perform binary search.... > > Regards, > Adi Srikanth. > Personal Pages: adisrikanth.co.nr > > > > > > > > On Fri, Sep 30, 2011 at 8:47 PM, Don <dondod...@gmail.com> wrote: > > @Ashima: It is a hypothetical question assuming an infinite array, > > which of course requires infinite memory. So don't worry about the > > compiler and other practical considerations. In real life the mass of > > the memory would cause it to collapse into a singularity long before > > the compiler would become an issue. Because we know that the array is > > sorted, we'll need a binary search at some point. But at first we > > don't know the bounds of the search. We must first find an index in > > the array which contains a value greater than or equal to the value > > we're searching for. Then we can do a binary search. To find that > > index, you could start at i=1 and double i until A[i] >= the value you > > are searching for. My method uses something like Newton's Method which > > will converge more quickly in some cases. It assumes that the slope is > > fairly consistent, which may or may not be a good assumption. > > > Don > > > On Sep 30, 10:00 am, "Ashima ." <ashima.b...@gmail.com> wrote: > > > isnt this quest a lil wrong. coz suppose if i dnt know the length of an > > > array,then how will i access the last element of the array.in such a > > > case,i will almost traverse the whole memory and still not stop. coz > > > compiler does not give array out of bound exception. > > > Ashima > > > M.Sc.(Tech)Information Systems > > > 4th year > > > BITS Pilani > > > Rajasthan > > > > On Fri, Sep 30, 2011 at 6:06 PM, pssaravanan > > > <saravananselvam...@gmail.com>wrote: > > > > > If the length of the array s not known,v could not apply the binary > > > > search to search for an element. i think following code will produce > > > > better solution. > > > > > i = 0; > > > > for(i = 0;A[i] < p&& A[i] !=NULL;i = (i+1)^2); > > > > j = i; > > > > i = sqrt(i)-1; > > > > applybinarysearch(i,j); > > > > > -- > > > > 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. > > > -- > > 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. -- 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.
