We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.
Friday, May 27, 2011
WAP to Find a Word in Dictionary at ith Position Efficiently
If you have a dictionary (sorted list of words) of unknown size and given a function which returns the word in the dictionary at a specified 'i'th location. Suggest an algorithm for finding a word.
We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.
We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment