在 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 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習