Sorry it is some not sum... Yes ,actually the array is infinite,has some 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, Nisha Subramanian <[EMAIL PROTECTED]> wrote: > > 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.Now the 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 -~----------~----~----~----~------~----~------~--~---
