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

Question

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

Answer 1

只是在未知移位后重新排序数组。这在计算上会很昂贵，但它是正确的。

此外，此时您也可以只进行线性排序，因为排序和搜索的时间复杂度为 O(n*log(n))。通过蛮力进行线性搜索只会是 O(n)。

Answer 2

方法一

实际上，对于一个未知的转变，你仍然可以做一个二进制，但它有点不稳定。

一种方法是将列表的大小加倍，即：

[4,5,6,   1,2,3, 4,5,6,   1,2,3]
# basically  mylist.extend(mylist)

如您所见，我只是将尺寸扩大了一倍，但中间部分仍然是有序的。

现在您可以浏览列表直到

list[i-1] > list[i]

这将是二分搜索的开始，末尾相同的数量将是二分列表的末尾。

start = i
end = len(list) -1

现在你可以进行二分查找了

根据数据平均值可能会低于 O(n)

方法二

您可以使用列表并进行二进制搜索：

O(nlog(n)) + log(n)

方法三

所有元素的线性搜索

O(n)

Answer 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次二分查找）。

Answer 4

只是简单的二分搜索，没有加倍或排序或任何其他数组预处理

让我们开始吧

l = 0; 
r = n-1;

和

m = (l + r)/2

如果我们正在搜索值 v 则：

1) 如果（l和m之间没有跳转）

array[l] < v < array[m] or

(如果l和m之间有跳转)

v < array[m] < array[l] or  
array[m] < array[l] < v

比起v在l和r之间，我们可以 r = m

2) 如果 v 等于 array[l] array[r] 或 array[m] 我们找到它

3) 在所有其他情况下，v 介于 m 和 r 之间，我们可以令 l = m

4) 重复新的 l 和 r

Answer 5

您只需要运行通过常规的二进制搜索算法一次，修改了何时 select 向上或向下搜索 window 的逻辑。修改是基于与移位数组中的第一个元素的额外比较，以便您知道您在数组的哪个段中。您可以执行此操作而无需实际找到拆分的精确位置。

在ruby中：

LIST = [6,7,8,9,10,1,2,3,4,5]

def binary_search(x)
  first = LIST[0]
  low = 0
  high = LIST.size-1
  while low <= high
    mid = low + (high-low)/2 # avoid overflow
    return mid if x == LIST[mid]
    if (LIST[mid] < first) != (x < first) || LIST[mid] < x
      low = mid + 1
    else
      high = mid - 1
    end
  end
  return -1 # not found
end

1.upto(10) do |x|
  puts "#{x} found at index #{binary_search(x)}"
end

输出：

1 found at index 5
2 found at index 6
3 found at index 7
4 found at index 8
5 found at index 9
6 found at index 0
7 found at index 1
8 found at index 2
9 found at index 3
10 found at index 4

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

Binary search modification on unknown shift

algorithm

search

方法一

方法二

方法三