使用二进制搜索查找旋转点，为什么要与第一个元素比较？

Question

所以我有从面试准备课程中购买的这个问题，这里也有解决方案。我了解我们正在使用二进制搜索来找到目标。数组包含不同的单词，目标是以a开头的单词。我最初的方法是与i-1和i + 1进行比较。如果i-1大于i并且i + 1小于i，那么我们知道我是目标。但是解决方案正在做我不理解的事情。问题出在这里

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",
};

Java
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.

解决方法如下

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;
}

我们为什么要与单词[0]进行比较？我们知道单词[0]并不是目标，因为它已经转移了。说我们有p，r，s，u，x，a，b，c，e，k，o。我们知道一个是中间的。由于p> a，我们将上限设置为a。然后，我们再次将p与s进行比较。所以它错过了目标。我只是不明白。请任何帮助将不胜感激

Answer 1

这样做是为了了解旋转点在哪里。

让我们看看您的示例：

String[] words = new String[]{
    "ptolemaic",
    "retrograde",
    "supplant",
    "undulate",
    "xenoepist",
    "asymptote",  // <-- rotates here!
    "babka",
    "banoffee",
    "engender",
    "karpatka",
    "othellolagkage",
};

比较words[0]（即ptolemaic）和words[guessIndex]（即asymptote）将告诉您阵列旋转/移位的方向。

可能有类似的东西：

[1 2 3 4 5 6 7] // no rotation

[6 7 1 2 3 4 5] // biggest is left to the center

[2 3 4 5 6 7 1] // smallest is right to the center

了解了您最大/最小的位置后，您可以了解继续搜索所需的方向。

希望这会有所帮助。

Answer 2

您确定解决方案是否正确？