C++ 在排序和旋转的数组中搜索

Searching in a sorted and rotated array

提问by Jones

While preparing for an interview I stumbled upon this interesting question:

在准备面试时，我偶然发现了一个有趣的问题：

You've been given an array that is sorted and then rotated.

For example:

• Let arr = [1,2,3,4,5], which is sorted
• Rotate it twice to the right to give [4,5,1,2,3].

Now how best can one search in this sorted + rotated array?

你得到了一个排序然后旋转的数组。

例如：

• 让arr = [1,2,3,4,5]，这是排序
• 将其向右旋转两次以得到[4,5,1,2,3]。

现在如何最好地在这个排序 + 旋转的数组中进行搜索？

One can unrotate the array and then do a binary search. But that is no better than doing a linear search in the input array, as both are worst-case O(N).

可以对数组进行旋转，然后进行二分查找。但这并不比在输入数组中进行线性搜索更好，因为两者都是最坏情况 O(N)。

Please provide some pointers. I've googled a lot on special algorithms for this but couldn't find any.

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

I understand C and C++.

我了解 C 和 C++。

回答by codaddict

This can be done in O(logN)using a slightly modified binary search.

这可以通过O(logN)使用稍微修改的二进制搜索来完成。

The interesting property of a sorted + rotated array is that when you divide it into two halves, atleast one of the two halves will always be sorted.

排序 + 旋转数组的有趣特性是，当你把它分成两半时，两半中至少有一个会被排序。

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

as seem right sub-array is not sorted while left sub-array is sorted.

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

If mid happens to be the point of rotation them both left and right sub-arrays will be sorted.

如果 mid 恰好是旋转点，它们的左右子数组都将被排序。

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

But in any case one half(sub-array) must be sorted.

但无论如何，必须对一半（子数组）进行排序。

We can easily know which half is sorted by comparing start and end element of each half.

通过比较每一半的开始和结束元素，我们可以很容易地知道哪一半被排序。

Once we find which half is sorted we can see if the key is present in that half - simple comparison with the extremes.

一旦我们找到哪一半被排序，我们就可以看到关键是否存在于那一半中——与极端情况进行简单的比较。

If the key is present in that half we recursively call the function on that half
else we recursively call our search on the other half.

如果键存在于那一半中，我们递归地调用那半上的函数，
否则我们递归地调用另一半上的搜索。

We are discarding one half of the array in each call which makes this algorithm O(logN).

我们在每次调用中丢弃数组的一半，这使得这个算法O(logN)。

Pseudo code:

伪代码：

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

The key here is that one sub-array will always be sorted, using which we can discard one half of the array.

这里的关键是总是对一个子数组进行排序，使用它我们可以丢弃数组的一半。

回答by ChuanRocks

The accepted answer has a bug when there are duplicate elements in the array. For example, arr = {2,3,2,2,2}and 3 is what we are looking for. Then the program in the accepted answer will return -1 instead of 1.

当数组中有重复元素时，接受的答案有一个错误。例如，arr = {2,3,2,2,2}3 是我们正在寻找的。然后接受答案中的程序将返回 -1 而不是 1。

This interview question is discussed in detail in the book 'Cracking the Coding Interview'. The condition of duplicate elements is specially discussed in that book. Since the op said in a comment that array elements can be anything, I am giving my solution as pseudo code in below:

这个面试问题在《破解编码面试》一书中有详细讨论。重复元素的条件在那本书中专门讨论过。由于 op 在评论中说数组元素可以是任何东西，我将我的解决方案作为下面的伪代码提供：

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[low])    
        // 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

回答by Max

You can do 2 binary searches: first to find the index isuch that arr[i] > arr[i+1].

您可以进行 2 次二分搜索：首先找到i使arr[i] > arr[i+1].

Apparently, (arr\[1], arr[2], ..., arr[i])and (arr[i+1], arr[i+2], ..., arr[n])are both sorted arrays.

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

Then if arr[1] <= x <= arr[i], you do binary search at the first array, else at the second.

然后 if arr[1] <= x <= arr[i]，您在第一个数组中进行二分搜索，否则在第二个数组中进行。

The complexity O(logN)

复杂性 O(logN)

EDIT: the code.

编辑： 代码。

回答by RomanK

My first attempt would be to find using binary search the number of rotations applied - this can be done by finding the index n where a[n] > a[n + 1] using the usual binary search mechanism. Then do a regular binary search while rotating all indexes per shift found.

我的第一次尝试是使用二分搜索找到应用的旋转次数 - 这可以通过使用通常的二分搜索机制找到 a[n] > a[n + 1] 的索引 n 来完成。然后进行常规二分搜索，同时轮换找到的每个班次的所有索引。

回答by Akki Javed

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

回答by Sebastian Paaske T?rholm

If you know that the array has been rotated s to the right, you can simply do a binary search shifted s to the right. This is O(lg N)

如果您知道数组已向右旋转 s，则可以简单地进行二分查找，将 s 向右移动。这是 O(lg N)

By this, I mean, initialize the left limit to s and the right to (s-1) mod N, and do a binary search between these, taking a bit of care to work in the correct area.

我的意思是，将左极限初始化为 s，将右极限初始化为 (s-1) mod N，并在它们之间进行二分搜索，注意在正确的区域中工作。

If you don't know how much the array has been rotated by, you can determine how big the rotation is using a binary search, which is O(lg N), then do a shifted binary search, O(lg N), a grand total of O(lg N) still.

如果不知道数组旋转了多少，可以使用二分查找来确定旋转的大小，即 O(lg N)，然后进行移位二分查找，O(lg N)，a仍然是 O(lg N) 的总和。

回答by Henk Holterman

If you know how (far) it was rotated you can still do a binary search.

如果你知道它是如何（远）旋转的，你仍然可以进行二分查找。

The trick is that you get two levels of indices: you do the b.s. in a virtual 0..n-1 range and then un-rotate them when actually looking up a value.

诀窍是你得到两个级别的索引：你在虚拟 0..n-1 范围内做 bs，然后在实际查找值时取消旋转它们。

回答by SivGo

You don't need to rotate the array first. You can use binary search on the rotated array (with some modifications).

您不需要先旋转阵列。您可以对旋转的数组使用二分搜索（进行一些修改）。

Let N be the number you are searching for:

设 N 为您要搜索的数字：

Read the first number (arr[start]) and the number in the middle of the array (arr[end]):

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

• if arr[start] > arr[end] --> the first half is not sorted but the second half is sorted:

  • if arr[end] > N --> the number is in index: (middle + N - arr[end])

  • if N repeat the search on the first part of the array (see end to be the middle of the first half of the array etc.)

• 如果 arr[start] > arr[end] --> 前半部分未排序但后半部分已排序：

  • 如果 arr[end] > N --> 数字在索引中：(middle + N - arr[end])

  • 如果 N 重复对数组的第一部分的搜索（见末尾是数组前半部分的中间等）

(the same if the first part is sorted but the second one isn't)

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

回答by NIKUNJ BHARTIA

Reply for the above mentioned post "This interview question is discussed in detail in the book 'Cracking the Coding Interview'. The condition of duplicate elements is specially discussed in that book. Since the op said in comment that array elements can be anything, I am giving my solution as pseudo code in below:"

回复上述帖子“这个面试题在《破解编码面试》一书中有详细讨论。重复元素的情况在那本书里有专门讨论。既然op在评论里说数组元素可以是任何东西，我我将我的解决方案作为下面的伪代码提供：”

Your solution is O(n) !! (The last if condition where you check both halves of the array for a single condition makes it a sol of linear time complexity )

你的解决方案是 O(n) !! （最后一个 if 条件，您检查数组的两半是否为单个条件使其成为线性时间复杂度的溶胶）

I am better off doing a linear search than getting stuck in a maze of bugs and segmentation faults during a coding round.

与在编码回合中陷入错误和分段错误的迷宫中相比，我最好进行线性搜索。

I dont think there is a better solution than O(n) for a search in a rotated sorted array (with duplicates)

我不认为有比 O(n) 更好的解决方案来搜索旋转排序数组（有重复）

回答by Chee Loong Soon

First, you need to find the shift constant, k. This can be done in O(lgN) time. From the constant shift k, you can easily find the element you're looking for using a binary search with the constant k. The augmented binary search also takes O(lgN) time The total run time is O(lgN + lgN) = O(lgN)

首先，您需要找到移位常数 k。这可以在 O(lgN) 时间内完成。从常数移位 k 中，您可以使用常数 k 使用二分搜索轻松找到您要查找的元素。增强二分查找也需要 O(lgN) 时间 总运行时间为 O(lgN + lgN) = O(lgN)

To find the constant shift, k. You just have to look for the minimum value in the array. The index of the minimum value of the array tells you the constant shift. Consider the sorted array [1,2,3,4,5].

要找到常数偏移，k。你只需要在数组中寻找最小值。数组最小值的索引告诉您常量移位。考虑排序数组 [1,2,3,4,5]。

The possible shifts are:
    [1,2,3,4,5] // k = 0
    [5,1,2,3,4] // k = 1
    [4,5,1,2,3] // k = 2
    [3,4,5,1,2] // k = 3
    [2,3,4,5,1] // k = 4
    [1,2,3,4,5] // k = 5%5 = 0 

To do any algorithm in O(lgN) time, the key is to always find ways to divide the problem by half. Once doing so, the rest of the implementation details is easy

要在 O(lgN) 时间内完成任何算法，关键是始终找到将问题除以一半的方法。一旦这样做，其余的实现细节就很容易了

Below is the code in C++ for the algorithm

下面是该算法的 C++ 代码

// This implementation takes O(logN) time
// This function returns the amount of shift of the sorted array, which is
// equivalent to the index of the minimum element of the shifted sorted array. 
#include <vector> 
#include <iostream> 
using namespace std; 

int binarySearchFindK(vector<int>& nums, int begin, int end)
{
    int mid = ((end + begin)/2); 
    // Base cases
    if((mid > begin && nums[mid] < nums[mid-1]) || (mid == begin && nums[mid] <= nums[end]))     
        return mid; 
    // General case 
    if (nums[mid] > nums[end]) 
    {
        begin = mid+1; 
        return binarySearchFindK(nums, begin, end); 
    }
    else
    {
        end = mid -1; 
        return binarySearchFindK(nums, begin, end); 
    }   
}  
int getPivot(vector<int>& nums)
{
    if( nums.size() == 0) return -1; 
    int result = binarySearchFindK(nums, 0, nums.size()-1); 
    return result; 
}

// Once you execute the above, you will know the shift k, 
// you can easily search for the element you need implementing the bottom 

int binarySearchSearch(vector<int>& nums, int begin, int end, int target, int pivot)
{
    if (begin > end) return -1; 
    int mid = (begin+end)/2;
    int n = nums.size();  
    if (n <= 0) return -1; 

    while(begin <= end)
    {
        mid = (begin+end)/2; 
        int midFix = (mid+pivot) % n; 
        if(nums[midFix] == target) 
        {
            return midFix; 
        }
        else if (nums[midFix] < target)
        {
            begin = mid+1; 
        }
        else
        {
            end = mid - 1; 
        }
    }
    return -1; 
}
int search(vector<int>& nums, int target) {
    int pivot = getPivot(nums); 
    int begin = 0; 
    int end = nums.size() - 1; 
    int result = binarySearchSearch(nums, begin, end, target, pivot); 
    return result; 
}

Hope this helps!=)
Soon Chee Loong, 
University of Toronto