পাইথন - বিটোনিক সিকোয়েন্সে বিটোনিক পয়েন্ট খুঁজে বের করা (বাইনারি সার্চ)

বিটোনিক সিকোয়েন্স (Bitonic Sequence) হলো এমন একটি সিকোয়েন্স যা প্রথমে স্ট্রিক্টলি ইনক্রিজিং (strictly increasing) হয়, তারপর একটি পয়েন্টে পৌঁছে স্ট্রিক্টলি ডিক্রিজিং (strictly decreasing) হয়। এই শিখর পয়েন্টটিকে বিটোনিক পয়েন্ট (Bitonic Point) বলা হয়। এই সমস্যাটি বাইনারি সার্চ দিয়ে O(log N)-এ সমাধান করা যায়।

সমস্যা বিবরণ

ইনপুট: [7, 8, 9, 12, 10, 6, 3, 2]
আউটপুট: 12

ব্যাখ্যা: ৭→৮→৯→১২ (ইনক্রিজিং), তারপর ১২→১০→৬→৩→২ (ডিক্রিজিং)। শিখর = ১২।

বাইনারি সার্চ অ্যালগরিদম

def find_bitonic_point(arr):
    """বিটোনিক অ্যারে থেকে পিক এলিমেন্ট বের করা O(log n)"""
    n = len(arr)
    if n < 3:
        return -1  # বিটোনিক পয়েন্টের জন্য কমপক্ষে ৩ এলিমেন্ট লাগে
    
    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  # বিটোনিক পয়েন্ট পাওয়া যায়নি

# টেস্ট
test_cases = [
    [7, 8, 9, 12, 10, 6, 3, 2],      # 12
    [1, 3, 5, 4, 2],                  # 5
    [10, 20, 30, 40, 50],             # -1 (শুধু ইনক্রিজিং)
    [50, 40, 30, 20, 10],             # -1 (শুধু ডিক্রিজিং)
    [1, 2, 3, 4, 5, 4, 3, 2, 1],      # 5
]

for arr in test_cases:
    result = find_bitonic_point(arr)
    print(f"Array: {arr} -> Bitonic Point: {result}")

আউটপুট

Array: [7, 8, 9, 12, 10, 6, 3, 2] -> Bitonic Point: 12
Array: [1, 3, 5, 4, 2] -> Bitonic Point: 5
Array: [10, 20, 30, 40, 50] -> Bitonic Point: -1
Array: [50, 40, 30, 20, 10] -> Bitonic Point: -1
Array: [1, 2, 3, 4, 5, 4, 3, 2, 1] -> Bitonic Point: 5

রিকারসিভ ভার্সন (মূল আর্টিকেল অনুযায়ী)

def binary_search_bitonic(arr, left, right):
    if left <= right:
        mid = (left + right) // 2
        
        if arr[mid - 1] < arr[mid] > arr[mid + 1]:
            return mid
        
        if arr[mid] < arr[mid + 1]:
            return binary_search_bitonic(arr, mid + 1, right)
        else:
            return binary_search_bitonic(arr, left, mid - 1)
    
    return -1

# ব্যবহার
arr = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(arr)
index = binary_search_bitonic(arr, 1, n - 2)
if index != -1:
    print(arr[index])  # 12

কেন বাইনারি সার্চ কাজ করে?

• বিটোনিক অ্যারেতে একটি নির্দিষ্ট প্রপার্টি রয়েছে: mid পয়েন্টে যদি arr[mid] < arr[mid+1] হয়, তবে পিক অবশ্যই ডান পাশে আছে (কারণ ইনক্রিজিং স্লপে আছি)।
• যদি arr[mid] > arr[mid+1] হয়, তবে পিক বাম পাশে আছে বা বর্তমান mid হয়তে পারে।
• এই প্রপার্টি বাইনারি সার্চের "ডিসিশন" নেওয়ার ভিত্তি তৈরি করে।

তুলনা: লিনিয়ার vs বাইনারি সার্চ