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

server side programmingprogrammingpython

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

因此，如果输入为 [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]);