So I have this question I purchased from interview preparation course and I have the solution here as well. I understand we are using binary search to find the target. the array contains different words and the target is the one that starts with a. my initial approach was to compare with i-l and i +1. if i - 1 is bigger than i and i+1 is lower than i then we know i is the target. But the solution is doing something I just don't understand. Here's the problem
I opened up a dictionary to a page in the middle and started flipping through, looking for words I didn't know. I put each word I didn't know at increasing indices in a huge array I created in memory. When I reached the end of the dictionary, I started from the beginning and did the same thing until I reached the page I started at.
Now I have an array of words that are mostly alphabetical, except they start somewhere in the middle of the alphabet, reach the end, and then start from the beginning of the alphabet. In other words, this is an alphabetically ordered array that has been "rotated." For example:
String[] words = new String[]{
"ptolemaic",
"retrograde",
"supplant",
"undulate",
"xenoepist",
"asymptote", // <-- rotates here!
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage",
};
Write a method for finding the index of the "rotation point," which is where I started working from the beginning of the dictionary. This array is huge (there are lots of words I don't know) so we want to be efficient here.
And the solution is the below
Solution This is a modified version of binary search. At each iteration, we go right if the item we're looking at is greater than the first item and we go left if the item we're looking at is less than the first item.
We keep track of the lower and upper bounds on the rotation point, calling them floorIndex and ceilingIndex (initially we called them "floor" and "ceiling," but because we didn't imply the type in the name we got confused and created bugs). When floorIndex and ceilingIndex are directly next to each other, we know the floor is the last item we added before starting from the beginning of the dictionary, and the ceiling is the first item we added after.
public static int findRotationPoint(String[] words) {
final String firstWord = words[0];
int floorIndex = 0;
int ceilingIndex = words.length - 1;
while (floorIndex < ceilingIndex) {
// guess a point halfway between floor and ceiling
int guessIndex = floorIndex + ((ceilingIndex - floorIndex) / 2);
// if guess comes after first word or is the first word
if (words[guessIndex].compareTo(firstWord) >= 0) {
// go right
floorIndex = guessIndex;
} else {
// go left
ceilingIndex = guessIndex;
}
// if floor and ceiling have converged
if (floorIndex + 1 == ceilingIndex) {
// between floor and ceiling is where we flipped to the beginning
// so ceiling is alphabetically first
break;
}
}
return ceilingIndex;
}
Why do we compare with words[0]? we know words[0] isn't the target since it's been shifted. say we have p, r, s, u, x, a, b, c ,e,k, o. we know a is the middle. since p > a, we set ceiling to be a. Then we again compare p with s. so it's missing the target. I just don;t understand this. please any help would be highly appreciated