সার্চিং ও সিলেকশন৬ মিনিট পড়া

এক্সপোনেনশিয়াল এবং ইন্টারপোলেশন সার্চ (Exponential & Interpolation Search)

প্রথমে পরিসীমা বা রেঞ্জ খুঁজে বের করুন, তারপর সেটিতে বাইনারি সার্চ চালান
time:\(O(\log n)\)space:\(O(1)\)best for:অজানা আকারের অ্যারে অথবা টার্গেট শুরুর কাছাকাছি থাকলে

কল্পনা করুন আপনি একটি রাস্তায় কোনো একটি বাড়ি খুঁজছেন, কিন্তু আপনি জানেন না রাস্তাটি ঠিক কত লম্বা। আপনি প্রথমে ১ পা নিলেন, তারপর ২ পা, তারপর ৪ পা, তারপর ৮ পা — প্রতিবার আপনার পদক্ষেপের আকার দ্বিগুণ করছেন — যতক্ষণ না আপনি আপনার গন্তব্যকে ছাড়িয়ে (overshoot) চলে যাচ্ছেন। এখন আপনি জানেন যে বাড়িটি অবশ্যই আপনার পার হওয়া শেষ গ্যাপের বা প্রসারণের ভেতরেই কোথাও আছে। এরপর আপনি সেই গ্যাপের শুরুতে ফিরে যান এবং সেখান হতে ঘর ধরে ধরে বা সাবধানে পুনরায় অনুসন্ধান শুরু করেন।

এটাই হলো এক্সপোনেনশিয়াল সার্চ। প্রথম পর্যায়: দ্বিগুণ হতে হতে লক্ষ্যকে অতিক্রম করুন। দ্বিতীয় পর্যায়: নির্ধারিত ক্ষুদ্র সীমার ভেতর বাইনারি সার্চ চালান।

কেন শুধু বাইনারি সার্চ নয়?

যখন আপনি অ্যারের আকার জানেন তখন বাইনারি সার্চ একদম নিখুঁত। কিন্তু কখনো কখনো আপনি আকার নাও জানতে পারেন — যেমন কোনো একটি সর্টেড ডেটা স্ট্রীম আসছে, অথবা এমন কোনো এপিআই (API) যা আপনাকে যেকোনো ইনডেক্স অ্যাক্সেস করতে দেয় কিন্তু মোট উপাদানের সংখ্যা জানায় না। আপনি যদি n নাই জানেন তবে আপনি hi = n - 1 সেট করতে পারবেন না।

এক্সপোনেনশিয়াল সার্চ এটি সমাধান করে: এটি দ্বিগুণ হওয়ার মাধ্যমে প্রথমে রেঞ্জ বা পরিসীমা আবিষ্কার করে, এবং তারপর সেটি সার্চ করে। এমনকি আরও ভালো ব্যাপার হলো — আপনার টার্গেট বা লক্ষ্য যদি শুরুর কাছাকাছি (যেমন পজিশন p-তে) থাকে, তবে পুরো অ্যারে যত বিশালই হোক না কেন আপনি মাত্র \(O(\log p)\) সময়ে সেটি খুঁজে পাবেন। বাইনারি সার্চের ক্ষেত্রে পূর্ণ অ্যারের সাইজ অনুযায়ী \(O(\log n)\) সময় লাগত যেখানে n \gg p।

দুটি পর্যায়

পর্যায় ১ — পরিসীমা নির্ধারণ (Bounding): ইনডেক্স ১ থেকে শুরু করুন। যদি arr[1] < target হয়, তবে ইনডেক্স ২-এ লাফ দিন, তারপর ৪, তারপর ৮, এভাবে প্রতিবার দ্বিগুণ করুন। যখন আপনি arr[i] >= target পাবেন অথবা অ্যারের সীমানা ছাড়িয়ে যাবেন তখন থামুন। আপনার টার্গেট অবশ্যই \([i/2, i]\) সীমার মধ্যে থাকবে।

পর্যায় ২ — বাইনারি সার্চ: এখন \([i/2, \min(i, n-1)]\) সীমার মধ্যে স্ট্যান্ডার্ড বাইনারি সার্চ চালান। যেহেতু এই পরিসরের আকার সর্বোচ্চ i/2 যা টার্গেটের পজিশনের কাছাকাছি বা সমান, তাই এই বাইনারি সার্চের খরচ হবে মাত্র \(O(\log p)\)।

সর্বমোট খরচ: বাউন্ডিংয়ের জন্য \(O(\log p)\) + বাইনারি সার্চের জন্য \(O(\log p)\) = \(O(\log p)\)। সাধারণত র্যান্ডম কোনো টার্গেটের জন্য p \approx n/2 হয়, তাই এটি গড়ে \(O(\log n)\)-এ রূপ নেয়।

দ্রষ্টব্য: এক্সপোনেনশিয়াল সার্চ তখন সবচেয়ে ভালো কাজ করে যখন টার্গেট বা লক্ষ্যটি তালিকার শুরুর কাছাকাছি থাকে। যদি আপনি কোনো সর্টেড কন্টাক্ট লিস্টে 'Asif' খুঁজছেন, তবে এক্সপোনেনশিয়াল সার্চ মাত্র কয়েক ধাপেই সেটি খুঁজে পাবে — অথচ বাইনারি সার্চকে তখনও তালিকার মাঝখানের কোনো বিন্দু থেকে চেক করা শুরু করতে হতো।

এক্সপোনেনশিয়াল সার্চ (Exponential Search)

def binary_search(arr, lo, hi, target):
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def exponential_search(arr, target):
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    # Double the range until we overshoot the target
    i = 1
    while i < n and arr[i] < target:
        i *= 2
    # Binary search within the determined small range
    return binary_search(arr, i // 2, min(i, n - 1), target)


arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
print(exponential_search(arr, 7))   # 3
print(exponential_search(arr, 10))  # -1
Output
3
-1

Complexity

🚀 পরিসীমা নির্ধারণ (Bounding phase)
\(p\) = টার্গেটের সূচক বা ইনডেক্স; লক্ষ্যকে ছাড়িয়ে যেতে মাত্র লগ p সংখ্যক দ্বিগুণ লাফ বা ড্রাবলিং প্রয়োজন
টার্গেট পজিশনের লগারিদম \(O(\log p)\)
🔍 বাইনারি সার্চ পর্যায়
নির্ধারিত পরিসীমাটির আকার \(\approx p\), তাই এখানে বাইনারি সার্চের খরচও হয় \(O(\log p)\)
নির্ধারিত সীমার লগারিদম \(O(\log p)\)
⚡ সর্বমোট (Total)
উভয় পর্যায় একত্রিত করলে; \(O(\log p)\) ≤ \(O(\log n)\)
টার্গেট পজিশনের সাপেক্ষে লগারিদমিক \(O(\log n)\)
💾 স্পেস (Space)
শুধুমাত্র হাতেগোনা কয়েকটি ইনডেক্স ভেরিয়েবল — কোনো অতিরিক্ত মেমোরির প্রয়োজন হয় না
ধ্রুবক বা কন্সট্যান্ট \(O(1)\)

ছোট কুইজ

এক্সপোনেনশিয়াল সার্চ বিশেষ করে তখনই সবচেয়ে বেশি দরকারী যখন:

পড়া চালিয়ে যান