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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
