algorithm - 未知移位的二进制搜索修改

假设我有一个排序的数组[1, 2, 3, 4, 5, 6]。我可以应用二进制搜索找到任何数字，但是如果我的排序数组向左移动了某个未知数字，我必须对二进制搜索逻辑进行什么修改。像[4, 5, 6, 1, 2, 3]一样。

最佳答案

我们可以使用二分查找法找到转变。我们需要找到小于给定数组的第一个元素的第一个数字。像这样的东西:

def getShift():
    if a[n - 1] > a[0]:
         return 0 // there is no shift
    low = 0 // definitely not less than a[0]
    high = n - 1 // definitely less than a[0]
    while high - low > 1:
        mid = (low + high) / 2
        if a[mid] < a[0]:
            high = mid
        else
            low = mid
    return high

现在知道了这种变化，因此我们可以在两个时间间隔内运行标准二进制搜索:[0, shift)和[shift, n - 1]。

时间复杂度为O(log n)(因为我们运行了3次二进制搜索)。

关于algorithm - 未知移位的二进制搜索修改，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28462547/