ค้นหาจุด bitonic ในลำดับ bitonic ที่กำหนดใน Python

สมมติว่าเรามีลำดับบิตโทนิก เราต้องหาจุดบิตโทนิกในนั้น อย่างที่เราทราบกันดีว่า Bitonic Sequence เป็นลำดับของตัวเลขซึ่งจะเพิ่มขึ้นอย่างมากในตอนแรก จากนั้นหลังจากจุดหนึ่งๆ ตัวเลขนั้นจะลดลงอย่างมาก จุดนี้เป็นจุดบิตโทนิก สำหรับลำดับที่เพิ่มขึ้นหรือลดลงเท่านั้น จะไม่มีจุดบิโตนิก

ดังนั้น หากอินพุตเป็น [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 + 1] แล้ว −
  • คืนสินค้า
• ถ้า array[m]
• return binary_search(array, m + 1, r)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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