@Vikas, refining ur idea:
start with index 1
if (found) return index
else index *=2
So we can find the range in O(logn).
Then do binary search in O(logn).
Total complexity logn :)
Cheers
Nikhil Jindal
Delhi College of Engineering
On Wed, Sep 22, 2010 at 1:05 PM, vikas kumar <vikas.kumar...@gmail.com>wrote:
> we can approach it like
> *lets start with index 0
> if (found) return index
> else
> index += INCR_;
>
> *we will try to increment with INCR_ until one of the following
> conditions met
> index goes out of bounds
> found the words which must come after the value eg "meet" should
> occur prior to "must"
> found the word itself
> *after above we will get some range to be searched for and we can
> apply linear or binary search to find the string
>
> the analysis will depend on the INCR_ and n values
>
> hence worst case complexity will be
> gertWordAt complexity multiplied by
> O(log INCR_ ) binary search after range selection
> O(n/INCR_) searchinh for finding the correct range
>
> Now you might want to have some logic to determine correct INCR_ value
> if your dictionary is really changing at high frequency ;)
>
>
>
> On Sep 22, 12:53 am, Minotauraus <anike...@gmail.com> wrote:
> > high= const.(10^const)
> >
> > What's const? The point of this isn't that it's a difficult prob to
> > solve. Point lies in working with the design to make this close to log
> > n.
> >
> > Define what value "const" holds.
> >
> > On Sep 21, 9:12 am, "coolfrog$" <dixit.coolfrog.div...@gmail.com>
> > wrote:
> >
> >
> >
> > > its dictionary means shorted ordered arry.
> > > let low = 1; and high= const.(10^const)
> >
> > > Boolean isWord(String word)
> > > { while(low <= high)
> > > { mid = (low+ high)/2;
> > > if(word = getWordAt(mid))
> > > return true;
> > > if( word > getWordAt(mid))
> > > { high = mid-1
> > > }
> > > else
> > > low = mid+1;
> > > }
> >
> > > }
> > > Its a simple Binary Search Algorithm ...
> > > who's complexity is O(log n) times.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
