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

Question

所以我有这个问题，我购买的面试准备课程，我有解决办法，在这里，以及。我知道我们在用二分搜索找到目标。数组包含不同的单词，目标是以。我最初的方法是比较i-l和i+1。如果i-1比i大，i+1比i小，那么我们就知道i是目标。但解决办法是做一些我不明白的事。问题就在这里

我把字典翻到中间的一页，开始翻阅，寻找我不认识的单词。我把我不认识的每个单词放在我在内存中创建的一个巨大数组中增加索引。当我读到字典的结尾时，我从头开始，做同样的事情，直到我读到我开始读的那一页。

现在我有一组单词，大部分是按字母顺序排列的，除了它们从字母表中间的某个地方开始，到达末尾，然后从字母表的开头开始。换句话说，这是一个按字母顺序排列的数组，被“旋转”了。例如：

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

  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。我们知道a是中间。自p>a起，我们将上限设为a。然后我们再比较p和S。所以它错过了目标。我就是不明白这一点。如有任何帮助，我将不胜感激

Answer 1

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

让我们看看你的例子：

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

比较字[0]（即托勒密)和字[guessIndex]（即渐近)将告诉您数组的旋转/移位方向。

[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