在一个已排序并旋转的数组中搜索

Question

在准备面试时，我遇到了这个有趣的问题:

你得到了一个已排序并旋转的数组。

例如:

• 让 arr = [1,2,3,4,5]，它是有序的
• 向右旋转两次，得到 [4,5,1,2,3]。

现在最好的方法是如何搜索这个已排序+旋转的数组呢？

可以先将数组旋转回来，然后进行二分查找。但这和在输入数组中进行线性搜索一样糟糕，因为两者的最坏情况都是O(N)。

请提供一些指针。我在谷歌上搜索了很多关于此的特殊算法，但找不到任何内容。

我懂C和C++。

- Jones

---

如果这是一项作业，请添加“homework”标签。这将鼓励人们给予您温和的推动，引导您朝着正确的方向前进，而不是发布可复制的答案。 - sbi

你知道这个数组旋转了多少次吗？ - Yochai Timmer

对于那么大的数组，你根本不需要担心。你真正的问题是什么？ - sbi

不，这不是作业。我不知道旋转的次数。而且，这个例子是为了保持简单。这个数组可能有数百万个元素。 - Jones

数组的值始终从1开始连续吗？还是可以包含任何值（包括重复值）？ - The Archetypal Paul

不，Paul，它们可以是任何东西。 - Jones

Answer 1

使用稍微修改过的二分查找算法可以在 O(logN) 的时间复杂度内完成。

一个已排序且旋转过的数组有一个有趣的属性，即当你将它分成两半时，至少其中一半总是有序的。

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

似乎右侧子数组未排序，而左侧子数组已排序。

如果中间点是旋转点，则左右两个子数组均已排序。

[6,7,8,9,1,2,3,4,5]
         ^

无论如何都必须对一半的子数组进行排序。

我们可以通过比较每个子数组的起始元素和结束元素来轻松确定哪一半已排序。

一旦我们找到了已排序的那一半，我们就可以查看该半部分中是否存在该关键字 - 只需将极端元素与其进行简单比较即可。

如果该关键字存在于该半部分，则在该半部分上递归调用该函数。
否则，我们会在另一半上递归调用搜索。

在每次调用中丢弃了其中一半的数组，这使得此算法具有O(logN)的时间复杂度。

伪代码：

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid])

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

关键在于一个子数组总是已经排好序的，利用这一点我们可以舍弃掉数组的一半。

- codaddict

---

简单、简洁、例子丰富为胜！ - Ashwin

对于类似在 {10, 15, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10} 中搜索 "15" 这样包含重复元素的数组，解决方案需要做出哪些改变？ - Shadab Ansari

一个已排序并旋转的数组有一个有趣的特性，那就是当你将其分成两半时，至少其中一半总是有序的。这将区分天才或经验丰富者和新手。谢谢，这一句话帮助我想象整个解决方案。 - wild_nothing

这是我能找到的最好的解释。 - Sam Kah Chiin

如果我尝试查找3，那么[1, 3]的输出是不正确的。 - Manjeet Thakur

Answer 2

被接受的答案在数组中存在重复元素时会有一个 bug。例如，当 arr = {2,3,2,2,2} 且我们要查找的是 3 时，被接受的答案将返回 -1 而不是 1。

这个面试问题在《Cracking the Coding Interview》一书中有详细讨论。该书专门讨论了重复元素的条件。由于楼主在评论中表示数组元素可以是任何值，因此我在下面提供了伪代码解决方案。

function search( arr[], key, low, high)

    if(low > high)
        return -1
    
    mid = (low + high) / 2
    
    if(arr[mid] == key)
        return mid

    // if the left half is sorted.
    if(arr[low] < arr[mid]) {

        // if key is in the left half
        if (arr[low] <= key && key <= arr[mid]) 
            // search the left half
            return search(arr,key,low,mid-1)
        else
            // search the right half                 
            return search(arr,key,mid+1,high)
        end-if

    // if the right half is sorted. 
    else if(arr[mid] < arr[high])    
        // if the key is in the right half.
        if(arr[mid] <= key && arr[high] >= key) 
            return search(arr,key,mid+1,high)
        else
            return search(arr,key,low,mid-1)
        end-if
   
    else if(arr[mid] == arr[low])
       
        if(arr[mid] != arr[high])
            // Then elements in left half must be identical. 
            // Because if not, then it's impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
            // Then we only need to search the right half.
            return search(arr, mid+1, high, key)
        else 
            // arr[low] = arr[mid] = arr[high], we have to search both halves.
            result = search(arr, low, mid-1, key)
            if(result == -1)
                return search(arr, mid+1, high, key)
            else
                return result
   end-if
end-function

- ChuanRocks

---

我认为你是唯一一个正确考虑了重复元素的人。但是你的方法不能保证对数时间复杂度。特别是在像5,5,5,5,5,5, ...（有很多修复）这样的输入上，以及5,1,5等情况下。 - Tomato

如果我们有重复元素，时间复杂度是多少？ - Prashanth Debbadwar

如果允许重复，则我认为它必须是线性的。考虑一个包含一个“2”的N个1的列表。它可以放在任何地方，并且它将是有效的输入。我们正在寻找那个2。无论我们考虑多大范围的M>2个数字，如果2不在任何一侧，我们就不能确定它是否包含在这些M个数字中。因此，您无法以任何有助于缩小搜索范围的方式进行搜索。 - Sopel

Answer 3

你可以进行2次二分查找：首先找到索引i使得arr[i]>arr[i+1]

显然，(arr\[1], arr[2], ..., arr[i])和(arr[i+1], arr[i+2], ..., arr[n])都是已排序的数组。

如果arr[1] <= x <= arr[i]，则在第一个数组执行二分查找，否则在第二个数组执行。

时间复杂度为O(logN)

编辑： 代码。

- Max

---

谢谢Max，但我不明白你将如何运用你的第一个二分查找？ - Jones

我的意思是，你的搜索关键词是什么？ - Jones

@Jones，编写代码比解释更容易。我编辑了回答，请查看链接。 - Max

为什么必须明确搜索“破坏点”？为什么不直接使用修改后的二分搜索来搜索元素，并同时检查“异常”？ - ruslik

我来晚了，被问了同样的问题，我没有用O(logn)解决它，我的解决方案比O(n)稍微好一点。我的方法是使用两个指针i = 0和j = size() - 1，在循环中检查arr[i] == key或arr[j] == key，如果找到则返回i或j并退出，否则增加i和减少j，退出条件是i < j，在这种情况下，如果关键字位于中间，则循环将在最坏情况下运行n/2次。 - Jaydeep Shil

当你搜索索引i，即枢轴点时，它如何变为O(logN)？如果输入是1,2,3,4,5,6,7,8,9，则必须遍历整个数组，这是O(N)，然后执行二分搜索。因此，总体复杂度将为O(N)。 - iwrestledthebeartwice

Answer 4

我的第一次尝试是使用二分查找来查找应用的旋转次数 - 这可以通过找到索引n，其中a [n] > a [n + 1]，使用通常的二分查找机制来完成。 然后，在找到每个偏移量时，执行常规的二分查找。

- RomanK

---

当使用二分查找算法查找旋转数字的数量时，您的搜索键是什么？ - Jones

@Jones：这将是一种修改过的二分查找。您正在寻找两个相邻值减少的点。猜测一个索引。如果该索引处的值大于数组中的第一个值，则继续在猜测的右侧查找。如果它小于第一个值，则继续在左侧查找。但是，如果您实际上不关心不连续性在哪里，只想执行搜索，则codaddict的答案更好。 - Steve Jessop

Answer 5

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

- Akki Javed

---

如上所述，这不会处理重复条目的情况。但是，如果元素是唯一的，这是一个非常简单的代码，因为它不进行任何递归。 - kaushal

Answer 6

如果你知道数组向右旋转了s个位置，你可以简单地对向右移动了s个位置的数组执行二分查找。时间复杂度为O(lg N)。

我的意思是将左边界初始化为s，将右边界初始化为(s-1) mod N，然后在这两者之间进行二分查找，需要注意在正确的区域内进行操作。

如果你不知道数组被旋转了多少个位置，你可以使用二分查找来确定旋转的大小，时间复杂度为O(lg N)，然后进行带有偏移量的二分查找，时间复杂度仍然是O(lg N)，总的时间复杂度为O(lg N)。

- Sebastian Paaske Tørholm

Answer 7

回复上述帖子：“这个面试问题在书中‘Cracking the Coding Interview’中有详细讨论。该书特别讨论了重复元素的条件。由于评论中的操作员说数组元素可以是任何东西，因此我在下面提供了伪代码作为我的解决方案：”

您的解决方案是O(n)！（最后一个if条件，在检查数组的两半部分是否满足单一条件时，使其成为线性时间复杂度的解）。

在编码轮中，我最好进行线性搜索，而不是陷入错误和分段错误的迷宫中。

我认为在旋转排序数组（有重复项）中进行搜索没有比O(n)更好的解决方案。

- NIKUNJ BHARTIA

Answer 8

如果您知道旋转了多少，仍然可以进行二分查找。

关键在于您获得了两个级别的索引：您在虚拟的0..n-1范围内执行b.s.，然后在实际查找值时将它们解除旋转。

- H H

Answer 9

您不需要先旋转数组。您可以在旋转后的数组上使用二分查找（进行一些修改）。

设N为您要查找的数字：

读取第一个数字（arr [start]）和数组中间的数字（arr [end]）：

- 如果arr [start]> arr [end] -> 第一半未排序，但第二半已排序： - 如果arr [end]> N-> 数字在索引处：（middle + N-arr [end]） - 如果N < arr [start]-> 在第一半数组上重复搜索（请参见end作为数组第一半中间等等）

（如果第一部分已排序但第二部分未排序，则相同）

- SivGo

Answer 10

对于一个包含重复元素的旋转数组，如果需要找到某个元素的第一次出现，可以使用以下过程（Java代码）：

public int mBinarySearch(int[] array, int low, int high, int key)
{
    if (low > high)
        return -1; //key not present

    int mid = (low + high)/2;

    if (array[mid] == key)
        if (mid > 0 && array[mid-1] != key)
            return mid;

    if (array[low] <= array[mid]) //left half is sorted
    {
        if (array[low] <= key && array[mid] >= key)
            return mBinarySearch(array, low, mid-1, key);
        else //search right half
            return mBinarySearch(array, mid+1, high, key);
    }
    else //right half is sorted
    {
        if (array[mid] <= key && array[high] >= key)
            return mBinarySearch(array, mid+1, high, key);
        else
            return mBinarySearch(array, low, mid-1, key);
    }       

}

这是对codaddict上述程序的改进。请注意以下附加的if条件：

if (mid > 0 && array[mid-1] != key)

- ranjeeth1978