未知班次的二进制搜索修改

Question

假设我有一个排序数组[1, 2, 3, 4, 5, 6].我可以应用二进制搜索来查找任何数字,但我的二进制搜索逻辑中需要做什么修改如果我的排序数组向左移动了一些未知数字.喜欢[4, 5, 6, 1, 2, 3].

Answer 1

1. 我们可以使用二分搜索找到班次.我们需要找到第一个小于给定数组的第一个元素的数字.像这样的东西:

   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
   

2. 现在知道转变,以便我们可以在两个时间间隔内运行标准二进制搜索:[0, shift)和[shift, n - 1].

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