在 Python 中查找给定双调序列中的双调点

假设我们有一个双调序列，我们需要找到其中的双调点。众所周知，双调序列是一个数字序列，它首先严格递增，然后在某个点之后严格递减。这个点就是双调点。对于仅递增或仅递减的序列，双调点不可用。

因此，如果输入类似于 [7, 8, 9, 12, 10, 6, 3, 2]，则输出将为 12

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数 binary_search(array, l, r)
• 如果 l <= r，则：
  • m := (l + r) // 2
• 如果 array[m - 1] < array[m] 且 array[m] > array[m + 1]，则：
  • 返回 m
• 如果 array[m] < array[m + 1]，则：
  • 返回 binary_search(array, m + 1, r)
• 否则
  • 返回 binary_search(array, l, m - 1)
• 返回 -1

示例

让我们看看下面的实现以获得更好的理解：

 在线演示

def binary_search(array, l, r):
   if (l <= r):
      m = (l + r) // 2;
      if (array[m - 1] < array[m] and array[m] > array[m + 1]):
         return m;
      if (array[m] < array[m + 1]):
         return binary_search(array, m + 1,r);
      else:
         return binary_search(array, l, m - 1);
   return -1;
array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array);
index = binary_search(array, 1, n-2);
if (index != -1):
   print(array[index]);

输入

[7, 8, 9, 12, 10, 6, 3, 2]

输出

12

Arnab Chakraborty

更新于: 2020-08-28

432 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习