java - 旋转有序数组搜索

Question

正在研究以下算法难题。发布问题陈述和解决方案。问题是，我们是否需要“搜索两半”部分来保证它的安全？或者当 a[left] == a[mid] 时，我们可以只搜索右边的部分而不检查是否 a[mid] == a[right] -- 因为什么时候a[left] == a[mid]，我认为左边的所有元素都是相等的，不能满足搜索条件找值。

更详细的说，我的意思是写 last else if as 是否安全，

else if (a[left] == a[mid]) {
            return search(a, mid + 1, right, x);
    }

问题陈述

给定一个由 n 个整数组成的排序数组，该数组已经旋转了未知次数，请编写代码找到一个元素 在数组中，你可能会假设数组最初是按升序排列的

例子， 输入 find 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} 输出，8(数组中5的索引)

代码

public static int search(int a[], int left, int right, int x) {
    int mid = (left + right) / 2;
    if (x == a[mid]) { // Found element
        return mid;
    }
    if (right < left) {
        return -1;
    }

    /* While there may be an inflection point due to the rotation, either the left or 
     * right half must be normally ordered.  We can look at the normally ordered half
     * to make a determination as to which half we should search. 
     */
    if (a[left] < a[mid]) { // Left is normally ordered.
        if (x >= a[left] && x < a[mid]) { 
            return search(a, left, mid - 1, x);
        } else {
            return search(a, mid + 1, right, x);
        }
    } else if (a[mid] < a[left]) { // Right is normally ordered.
        if (x > a[mid] && x <= a[right]) {
            return search(a, mid + 1, right, x);
        } else {
            return search(a, left, mid - 1, x);
        }               
    } else if (a[left] == a[mid]) { // Left is either all repeats OR loops around (with the right half being all dups)
        if (a[mid] != a[right]) { // If right half is different, search there
            return search(a, mid + 1, right, x);
        } else { // Else, we have to search both halves
            int result = search(a, left, mid - 1, x); 
            if (result == -1) {
                return search(a, mid + 1, right, x); 
            } else {
                return result;
            }
        }
    }
    return -1;
}

Answer 1

就您的问题而言，您的假设是完全正确的，您不必在那里搜索两半。您可以只搜索右半部分，因为 if a[mid] != key ，你的元素肯定在右半部分，如果它在数组中的话。

编辑:

以上结论是不完整的。我现在写了一个新的，对此有一些进一步的思考。

首先，如果在任何时候，您都在搜索两半，那么进行二分搜索是没有意义的，因为搜索的复杂性变为 O(n) .

现在，如果a[mid] == a[left]，你就在那里，你的 key 可以在任何一半。但是，您可以确定的一件事是，其中一半的所有元素都相等。

eg. Suppose a[12] = [1,1,1,2,2,2,2,2,2,2,2,2]
    rotate r=2 times, a`[12] = [2,2,1,1,1,2,2,2,2,2,2,2]
    so, a[mid] = a[left] = 2
    if key = 1, it is in left half.

    now, rotate r=9 times,
         a``[12] = [2,2,2,2,2,2,2,2,2,1,1,1]
    so, a[mid] = a[left] = 2
    if key = 1, it is in right half

因此，您需要在该数组的两半中搜索您的 key ，这种情况实际上使二进制搜索变得多余。

So, now, I'd even propose you use the solution I mentioned below.

虽然如果没有限制，我想提出一个解决方案:

这是 Binary Search 的简单变体算法。

您首先必须在数组中应用二进制搜索，终止条件为:

a[mid-1] > a[mid]

一旦满足这个条件，你就有了索引 k = mid ，这会为您提供 2 个排序数组。

第一个数组，A[0...k-1]第二个数组，A[k...n-1] ，假设 n元素。

现在，检查一下。

if(key > A[0])
    Binary Search in A[0...k-1]
else
    Binary Search in A[k...n-1]

一个异常(exception)，如果数组已经旋转 n次，您不会得到 k 的值.对整个数组进行二进制搜索。

EDIT2: 从评论中回答您的问题

I am wondering for my original method if a[left] < a[mid], and x >= a[left] && x < a[mid], if it safe to search only on left side using search(a, left, mid - 1, x);, if the array may be rotated n times?

如果a[left] < a[mid] , 那么我们可以确定 a[left...mid]是升序排列的(已排序)。所以，如果 x >= a[left] && x < a[mid] , 只搜索左半边就够了。

if you could also clarify when a[left] == a[mid], and a[mid] == a[right] , we need to search both directions?

是的。在这种情况下，我们需要搜索两个方向。说，例如。您的原始数组是 {1,2,2,2,2,2,2,2,2,2}旋转一次。数组变为，{2,1,2,2,2,2,2,2,2,2} .如果旋转8次，则变成{2,2,2,2,2,2,2,2,1,2} .现在，如果您的搜索关键字是 1 , 就在开始的时候，在这两种情况下，a[mid] == a[left] == a[right] ，而你的 key 在不同的两半。因此，您需要在两半中搜索 key 。