Yes ,actually the array is infinite,has sum n elements in sorted order ,may not be continous and if the array has invalid numbers it has -1 in it.Nowthe task is to find a given valid number.Pls help me out now?
On 5/7/07, Arun <[EMAIL PROTECTED]> wrote: > > 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 [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 -~----------~----~----~----~------~----~------~--~---
