Tìm điểm bitonic trong chuỗi bitonic đã cho bằng Python

Giả sử chúng ta có một chuỗi bitonic, chúng ta phải tìm Điểm Bitonic trong đó. Như chúng ta đã biết Bitonic Sequence là một dãy số đầu tiên sẽ tăng dần, sau đó sau một thời điểm nhất định, nó sẽ giảm dần. Điểm này là điểm bitonic. Đối với chỉ chuỗi tăng hoặc chỉ giảm, điểm bitonic không có sẵn.

Vì vậy, nếu đầu vào là [7, 8, 9, 12, 10, 6, 3, 2], thì đầu ra sẽ là 12

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• xác định một hàm binary_search (mảng, l, r)
• nếu l <=r, thì -
  • m:=(l + r) / / 2
• nếu mảng [m - 1] mảng [m + 1], thì -
  • trả lại m
• nếu mảng [m]
• trả về binary_search (mảng, m + 1, r)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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]);

Đầu vào

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

Đầu ra

12