Python - หา Bitonic Point ใน Bitonic Sequence

Bitonic Sequence คือลำดับตัวเลขที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) ก่อน แล้วตามด้วยลดลงอย่างเคร่งครัด (strictly decreasing) จุดเปลี่ยนทิศทางนี้เรียกว่า Bitonic Point ลำดับที่เพิ่มขึ้นอย่างเดียวหรือลดลงอย่างเดียว ไม่มี bitonic point

ตัวอย่าง

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

Output: 12

อัลกอริธึม: Binary Search (O(log n))

def binary_search_bitonic(arr, left, right):
    """หา bitonic point ด้วย binary search"""
    if left <= right:
        mid = (left + right) // 2
        
        # ตรวจสอบว่า mid เป็น peak หรือไม่
        if arr[mid - 1] < arr[mid] and arr[mid] > arr[mid + 1]:
            return mid
        
        # ถ้าอยู่ในช่วงเพิ่มขึ้น → peak อยู่ขวา
        if arr[mid] < arr[mid + 1]:
            return binary_search_bitonic(arr, mid + 1, right)
        
        # ถ้าอยู่ในช่วงลดลง → peak อยู่ซ้าย
        else:
            return binary_search_bitonic(arr, left, mid - 1)
    
    return -1

def find_bitonic_point(arr):
    """Wrapper function"""
    n = len(arr)
    if n < 3:
        return -1  # ต้องมีอย่างน้อย 3 elements
    index = binary_search_bitonic(arr, 1, n - 2)
    return arr[index] if index != -1 else -1

# ทดสอบ
array = [7, 8, 9, 12, 10, 6, 3, 2]
result = find_bitonic_point(array)
print(f"Bitonic point: {result}")  # 12

Iterative Version (ไม่ใช้ Recursion)

def find_bitonic_point_iterative(arr):
    n = len(arr)
    left, right = 1, n - 2
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid - 1] < arr[mid] > arr[mid + 1]:
            return arr[mid]
        elif arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

กรณีพิเศษและ Edge Cases

# ทดสอบกรณีต่างๆ
test_cases = [
    [1, 3, 5, 4, 2],      # Normal: 5
    [1, 2, 3, 4, 5],      # Strictly increasing: -1
    [5, 4, 3, 2, 1],      # Strictly decreasing: -1
    [1, 3, 5, 5, 3, 1],   # Not strictly (duplicate): -1
    [10],                 # Too short: -1
    [1, 2],               # Too short: -1
]

for arr in test_cases:
    print(f"{arr} -> {find_bitonic_point(arr)}")

ผลลัพธ์

[1, 3, 5, 4, 2] -> 5
[1, 2, 3, 4, 5] -> -1
[5, 4, 3, 2, 1] -> -1
[1, 3, 5, 5, 3, 1] -> -1
[10] -> -1
[1, 2] -> -1

การประยุกต์ใช้

• หาค่าสูงสุดใน unimodal function (Ternary search alternative)
• Optimization problems
• Signal processing (peak detection)
• Bitonic sort algorithm

ความซับซ้อน

• Time: O(log n) - Binary search
• Space: O(log n) recursive / O(1) iterative