we can use a modified binary search to find the element. whenever u calculate a new lower and upper boundary you can move them forward and backward respectively so that both point to a index which contains a valid number.But still this wont give O(n).
do we have any memory constraints? do we have any other auxillary information available, might a table containing start and end indices of valid values? it seems O(n) is simple not possible without any additional info....assume you have only 1 valid element in the infinitely large array.you cant find that element in O(1) with out any additional info. correct me if i am wrong. Arun. On 5/7/07, Nisha Subramanian <[EMAIL PROTECTED]> wrote: > > 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.Now the 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 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 -~----------~----~----~----~------~----~------~--~---
