Find Index of a key

A function GetWordFromList takes an integer parameter and returns the word at the corresponding index. Now you are given a word,say "string", how do you optimally get the index of the word where it occurs. You don't know the data structure used to store the words.Assume that all the words in list/database are sorted.Also assume that the function returns null or some exception if the index which is given as input is out of bound.


Approach:
1. Suppose the list is an array (just of argument sake).
2. Let the array be 
String [] A = { "apple",
"boy",
"chair",
"dear",
"dog",
"eating",
"feature",
"great",
"heat",
"hunter",
"intelligent",
"jealous",
"joker",
"kites",
"least",
"light",
"meaning",
"money",
"name",
"neat",
"operation",
"peace",
"polite",
"quite",
"relentless",
"string",
"temperature",
"tools"
"universe",
"volvo",
"wax",
"xeon",
"year",
"zebra"
 }
Length of the array is 34.
3. Now lets start searching from 0th index and let first and lsst be variables init to 1.
4. keep doubling "last" and setting first to last, till our search key falls in the "first" and "last" range.
5. So if we try to trace "money" position in array A, we will have following values for first and last.
first = 1, last = 1;
first = 1, last = 2;
first = 2, last = 4;
first = 4, last = 8;
first = 8, last = 16;
first = 16, last = 32; -> "money" occurs in this range.


Now we we will do binary search in the range of A[16] and A[32] to locate the string "money".


Time complexity - O(logn) to find the range + O(logk) - (assuming k is the length of the range where the search key occurs).


Code output:
Length of Array: 34
Index of "money": 17
Index of "zebra": 33
Index of "boy": 1
Index of "volvo": 29
Index of "baby": -1