BiGYan, I think ur solution will not work as u r assuming the the "valid" numbers are stored contigously and n>inc
> while ( arr[i].val<=s ) > i+=inc; I think the question can be rephrased as a very large array of size N, has n valid numbers (n<<N) which are sorted(need not be contigous). Task is to find if s is present in O(n) I think u wanted to say something like increment step by 'inc', look "around" if u can find a valid value and then step forward or back. This is only sol'n I can think of too. Its only a heuristic, complexity is still O(N), not O(n). On 5/6/07, BiGYaN <[EMAIL PROTECTED]> wrote: > > > Infinite Array ? > Infinite Array in sorted order ? > > Let's say we have an infinite array where each of the elements have a > number (according to which it is sorted) and a valid/invalid bit for > storing the validity. > > s - number we are searching for > arr[] - the infinite array > > inc = 100; // this is the value you gotta tweak > i=0; > while ( arr[i].val<=s ) > i+=inc; > > if ( i==0 ) > // value not found > else > binary_search(arr[],i-inc,i,s); // arr[], low_lim, hi_lim, > search_number > > Guess this is the best that you could get. > But I'm still confused about that "Infinite Array". > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
