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

Question

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

您已经获得了一个已排序然后旋转的数组.

例

让arr = [1,2,3,4,5]哪个被排序然后旋转说两次给右边

[4,5,1,2,3]

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

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

请提供一些指示.我已经搜索了很多特殊算法,但找不到任何算法.

我理解c和c ++

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

因为看起来正确的子数组没有排序,而左子数组是排序的.

如果mid恰好是旋转点,则左右子阵列将被排序.

[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

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

Answer 2

你可以做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)

编辑: 代码.

Answer 3

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

这个面试问题在"破解编码面试"一书中有详细讨论.该书中特别讨论了重复元素的条件.由于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

Answer 4

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

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