as the array is infinitely large it is useful to maintain an auxiliary table which is a list of starting and ending indices of valid values.
Say you have an array like this : -1 1 2 -1 -1 -1 6 7 -1 -1 -1 10 -1 12 15 -1 [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15] =>indices array size : 16 aux table will be 1 2 6 7 11 11 13 14 now do a binary search on the aux table entries. find the start and end indices where the element could be and again do a binary search between start and end indices and locate the element. Arun On 5/7/07, Nisha Subramanian < [EMAIL PROTECTED]> wrote: > > Okie... if not O(n) how can u solve it in min order ..at any cost it > shouldn't turn out to be an infinite order.Is their any way Now? > > On 5/7/07, arun kumar manickan <[EMAIL PROTECTED]> wrote: > > > > 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 -~----------~----~----~----~------~----~------~--~---
