在排序和旋转数组中搜索。

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

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

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

你得到了一个数组，它被排序然后旋转。

example

例子

Let arr = [1,2,3,4,5] which is sorted and then rotated say twice to the right to give

让arr =[1,2,3,4,5]排序，然后旋转两次，表示给予的权利。

[4,5,1,2,3]

(4、5、1、2、3)

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

那么如何在这个有序的+旋转的数组中进行搜索呢?

One can unrotate the array and then do a binary search. But it is no better than doing a linear search in the input array as both are worst case 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++。

18 个解决方案

#1

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.

如果中间恰好是旋转的点，那么左右子数组就会被排序。

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

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

但在任何情况下，必须对1 / 2(子数组)进行排序。

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 hald..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if righ 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.

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

#2

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

你可以做2个二进制的搜索:首先找到我的索引，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.

如果arr[1] <= x <= arr[i]，则在第一个数组中进行二进制搜索，在第二个数组中进行。

The complexity O(logN)

复杂性O(logN)

EDIT: the code.

编辑:代码。

#3

The selected 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 selected 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 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

#4

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.

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

#5

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)

如果你知道数组已经被旋转到右边，你可以简单地做一个二分查找移到右边。这是O(log 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(lgn)，然后做一个移位的二分查找，O(lgn)，仍然是O(lgn)的总数。

#6

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中做b.s。n-1范围，然后在实际查找值时取消旋转。

#7

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

你不需要先旋转数组，你可以在旋转的数组上使用二分查找(有一些修改)

assume N is the number you search 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:

  如果arr[启动]> arr[end] ->，前半部分未排序，但下半部分已排序:

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

    如果arr[end] > N ->的数字为索引:(中+ 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.)

    如果N重复该数组的第一部分的搜索(请参见末尾是数组的前半部分的中间部分)。

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

(如果第一部分是排序的，但第二部分没有排序)

#8

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

#9

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) !!(最后一个条件，如果你检查数组的两个部分的单个条件，使它成为线性时间复杂度的sol)

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

我最好是做线性搜索，而不是在编码过程中陷在bug和分割错误的迷宫中。

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

我认为没有比O(n)更好的解决方案了，在旋转的排序数组中搜索(有重复的)

#10

public class PivotedArray {

//56784321 first increasing than decreasing
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] data ={5,6,7,8,4,3,2,1,0,-1,-2};

    System.out.println(findNumber(data, 0, data.length-1,-2));

}

static int findNumber(int data[], int start, int end,int numberToFind){

    if(data[start] == numberToFind){
        return start;
    }

    if(data[end] == numberToFind){
        return end;
    }
    int mid = (start+end)/2;
    if(data[mid] == numberToFind){
        return mid;
    }
    int idx = -1;
    int midData = data[mid];
    if(numberToFind < midData){
        if(midData > data[mid+1]){
            idx=findNumber(data, mid+1, end, numberToFind);
        }else{
            idx =  findNumber(data, start, mid-1, numberToFind);
        }
    }

    if(numberToFind > midData){
        if(midData > data[mid+1]){
            idx =  findNumber(data, start, mid-1, numberToFind);

        }else{
            idx=findNumber(data, mid+1, end, numberToFind);
        }
    }
    return idx;
}

}

#11

short mod_binary_search( int m, int *arr, short start, short end)
{

 if(start <= end)
 {
    short mid = (start+end)/2;

    if( m == arr[mid])
        return mid;
    else
    {
        //First half is sorted
        if(arr[start] <= arr[mid])
        {
            if(m < arr[mid] && m >= arr[start])
                return mod_binary_search( m, arr, start, mid-1);
            return mod_binary_search( m, arr, mid+1, end);
        }

        //Second half is sorted
        else
        {
            if(m > arr[mid] && m < arr[start])
                return mod_binary_search( m, arr, mid+1, end);
            return mod_binary_search( m, arr, start, mid-1);
        }
    }
 }
 return -1;
}

#12

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来搜索。

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 

#13

Here is a simple (time,space)efficient non-recursive O(log n) python solution that doesn't modify the original array. Chops down the rotated array in half until I only have two indices to check and returns the correct answer if one index matches.

这里有一个简单的(时间、空间)高效的非递归O(log n) python解决方案，它不会修改原始数组。将旋转的数组切成两半，直到我只有两个索引来检查并返回正确的答案，如果一个索引匹配。

def findInRotatedArray(array, num):

lo,hi = 0, len(array)-1
ix = None


while True:


    if hi - lo <= 1:#Im down to two indices to check by now
        if (array[hi] == num):  ix = hi
        elif (array[lo] == num): ix = lo
        else: ix = None
        break

    mid = lo + (hi - lo)/2
    print lo, mid, hi

    #If top half is sorted and number is in between
    if array[hi] >= array[mid] and num >= array[mid] and num <= array[hi]:
        lo = mid

    #If bottom half is sorted and number is in between
    elif array[mid] >= array[lo] and num >= array[lo] and num <= array[mid]:
        hi = mid


    #If top half is rotated I know I need to keep cutting the array down
    elif array[hi] <= array[mid]:
        lo = mid

    #If bottom half is rotated I know I need to keep cutting down
    elif array[mid] <= array[lo]:
        hi = mid

print "Index", ix

#14

Another approach that would work with repeated values is to find the rotation and then do a regular binary search applying the rotation whenever we access the array.

另一种处理重复值的方法是查找旋转，然后在每次访问数组时进行常规的二进制搜索。

test = [3, 4, 5, 1, 2]
test1 = [2, 3, 2, 2, 2]

def find_rotated(col, num):
    pivot = find_pivot(col)
    return bin_search(col, 0, len(col), pivot, num)

def find_pivot(col):
    prev = col[-1]
    for n, curr in enumerate(col):
        if prev > curr:
            return n
        prev = curr
    raise Exception("Col does not seem like rotated array")

def rotate_index(col, pivot, position):
    return (pivot + position) % len(col)

def bin_search(col, low, high, pivot, num):
    if low > high:
        return None
    mid = (low + high) / 2
    rotated_mid = rotate_index(col, pivot, mid)
    val = col[rotated_mid]
    if (val == num):
        return rotated_mid
    elif (num > val):
        return bin_search(col, mid + 1, high, pivot, num)
    else:
        return bin_search(col, low, mid - 1,  pivot, num)

print(find_rotated(test, 2))
print(find_rotated(test, 4))
print(find_rotated(test1, 3))

#15

Try this solution

试试这个解决方案

bool search(int *a, int length, int key)
{
int pivot( length / 2 ), lewy(0), prawy(length);
if (key > a[length - 1] || key < a[0]) return false;
while (lewy <= prawy){
    if (key == a[pivot]) return true;
    if (key > a[pivot]){
        lewy = pivot;
        pivot += (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}
    else{
        prawy = pivot;
        pivot -= (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}}
return false;
}

#16

For a rotated array with duplicates, if one needs to find the first occurrence of an element, one can use the procedure below (Java code):

对于具有重复的旋转数组，如果需要找到元素的第一个出现，可以使用下面的过程(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);
    }       

}

This is an improvement to codaddict's procedure above. Notice the additional if condition as below:

这是对上瘾者程序的改进。请注意以下附加条件:

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

#17

My simple code :-

我的简单代码:-

public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]> nums[r]){
            if(target > nums[mid] || nums[r]>= target)l = mid+1;
            else r = mid-1;
        }
        else{
            if(target <= nums[r] && target > nums[mid]) l = mid+1;
            else r = mid -1;
        }
    }
    return -1;
}

Time Complexity O(log(N)).

时间复杂度O(log(N))。

#18

This code in C++ should work for all cases, Although It works with duplicates, please let me know if there's bug in this code.

这个c++代码应该适用于所有的情况，尽管它使用的是副本，请让我知道代码中是否存在bug。

#include "bits/stdc++.h"
using namespace std;
int searchOnRotated(vector<int> &arr, int low, int high, int k) {

    if(low > high)
        return -1;

    if(arr[low] <= arr[high]) {

        int p = lower_bound(arr.begin()+low, arr.begin()+high, k) - arr.begin();
        if(p == (low-high)+1)
            return -1;
        else
            return p; 
    }

    int mid = (low+high)/2;

    if(arr[low] <= arr[mid]) {

        if(k <= arr[mid] && k >= arr[low])
            return searchOnRotated(arr, low, mid, k);
        else
            return searchOnRotated(arr, mid+1, high, k);
    }
    else {

        if(k <= arr[high] && k >= arr[mid+1])
            return searchOnRotated(arr, mid+1, high, k);
        else
            return searchOnRotated(arr, low, mid, k);
    }
}
int main() {

    int n, k; cin >> n >> k;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i];
    int p = searchOnRotated(arr, 0, n-1, k);
    cout<<p<<"\n";
    return 0;
}