找到列表中的下降.这可以在O(log n)中完成吗？

Question

我有一个整数列表,我试图通过使用递归算法来识别整数列表中的倾角来实现O(log n).下降是紧随其后的任何数字,并且遵循等于或大于其自身的数字,并且遵循,使得x> = dip <= y.只要它们旁边的数字大于或等于这些元素,就可以将第一个和最后一个元素视为倾角.

我已经能够通过简单地遍历列表来实现O(n),但是我正在尝试使用类似于二进制搜索算法的方法来实现更快的结果.我只需要在列表中找到一个下降点.

我的问题是当我将列表分成中点的左侧和右侧时,我最终会使用一个/两个元素到达较小的列表,但它们不一定是坑,因为它们没有考虑到它们切片之外的数字.

谁能帮我？

def find_dip(lst):
     if len(lst) == 1:
          return 0
     elif len(lst) == 2:
          if lst[0] <= lst[1]:
               return 0
          else:
               return 1
     else:
          ans = False
          mid = len(lst) // 2
          print("test")
          if lst[mid-1] >= lst[mid] <= lst[mid+1]:
               ans = mid
          elif ans == False and len(lst[mid:]) > 2:
               if lst[mid] >= lst[mid+1] <= lst[mid+2]:
                    ans = mid+1
          elif ans == False and len(lst[:mid]) > 2:
               if lst[mid-2] >= lst[mid-1] <= lst[mid]:
                    ans = mid-1      
          elif ans == False:
               ans = find_dip(lst[:mid])
          else:
               ans = find_dip(lst[mid+1:])
          return ans

Answer 1

答案是肯定的.基于以下链接找到峰值(与倾角完全相反)需要O(log n)时间.但是差异是肤浅的,所描述的算法可以以完全相似的方式进行调整.这是一个python版本:

def find_dip(lst):
    start, end = 0, len(lst) - 1
    while start < end:
        if end - start == 1: return start if lst[start] <= lst[end] else end
        mid = (start + end) / 2
        a, b, c = lst[mid - 1: mid + 2]
        if a >= b <= c: return mid
        if a <= b: end = mid - 1
        else: start = mid + 1
    return end