الگوریتم جستجوی ترتیبی (Interpolation Search)

در علم کامپیوتر و الگوریتم‌ها، جستجوی ترتیبی یکی از روش‌های اصلی برای یافتن مقدار خاص در یک مجموعه داده مرتب است. یکی از نسخه‌های بهبود یافته این الگوریتم، جستجوی ترتیبی با استفاده از فرمول ترتیبی یا به اصطلاح “Interpolation Search” است. این الگوریتم با توجه به توزیع یکنواخت داده‌ها در مجموعه، به شکل بهینه‌تری به جستجوی هدف می‌پردازد.

عملکرد الگوریتم:

در جستجوی ترتیبی معمولی، محاسبه موقعیت میانگین در دنباله انجام می‌شود. اما در جستجوی ترتیبی با استفاده از فرمول ترتیبی، ما از یک فرض قدرت‌مندتر برای تخمین موقعیت اولیه استفاده می‌کنیم. این فرمول به شکل زیر است:

که در آن:

• ( pos ) موقعیت مورد نظر برای جستجو است.
• ( low ) و ( high ) به ترتیب نشان‌دهنده حدین پایین و بالای دنباله هستند.
• ( key ) مقداری است که به دنبال آن هستیم.
• ( arr[] ) دنباله مرتب شده است.

مراحل الگوریتم:

1. محاسبه موقعیت تخمینی ( pos ) با استفاده از فرمول ترتیبی.
2. بررسی اینکه آیا ( arr[pos] ) برابر با ( key ) است یا خیر.
   • اگر برابر بود، مقدار یافت شده و الگوریتم پایان می‌یابد.
   • اگر کمتر بود، جستجو در زیردنباله‌ای که شامل ( arr[low] ) تا ( arr[pos-1] ) است انجام می‌شود.
   • اگر بزرگتر بود، جستجو در زیردنباله‌ای که شامل ( arr[pos+1] ) تا ( arr[high] ) است انجام می‌شود.

مزایا و معایب:

• مزایا:
  • کارایی بهتر نسبت به جستجوی ترتیبی معمولی، به ویژه زمانی که داده‌ها موزون توزیع شده باشند.
  • به عنوان یک الگوریتم بهینه سازی‌شده در بسیاری از موارد جستجو عملکرد مناسبی ارائه می‌دهد.
• معایب:
  • در مواردی که داده‌ها به طور نامتوازن توزیع شده باشند، ممکن است عملکرد آن ضعیفتر از جستجوی ترتیبی معمولی باشد.
  • نیاز به مرتب بودن داده‌ها دارد.

جستجوی ترتیبی با استفاده از فرمول ترتیبی یک الگوریتم جستجوی پیشرفته است که در بسیاری از موارد بهبود کارایی جستجوی ترتیبی معمولی را ارائه می‌دهد. با این حال، محدودیت‌های خود را دارد و برای استفاده موثر، می‌بایست مشخصات داده‌ها را در نظر گرفت و شرایط مورد نیاز برای استفاده از این الگوریتم را بررسی کرد.

در زیر یک نمونه کد پایتون برای الگوریتم جستجوی ترتیبی با استفاده از فرمول ترتیبی (Interpolation Search) آورده شده است:

def interpolation_search(arr, key):
    low, high = 0, len(arr) - 1

    while low <= high and arr[low] <= key <= arr[high]:
        pos = low + ((key - arr[low]) * (high - low)) // (arr[high] - arr[low])

        if arr[pos] == key:
            return pos
        elif arr[pos] < key:
            low = pos + 1
        else:
            high = pos - 1

    return -1  # اگر عنصر یافت نشد

# مثال:
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
search_key = 6
result = interpolation_search(sorted_array, search_key)

if result != -1:
    print(f"عنصر {search_key} یافت شد در موقعیت {result}")
else:
    print(f"عنصر {search_key} یافت نشد")

در این مثال، تابع interpolation_search یک آرایه مرتب شده و یک عدد به عنوان ورودی می‌گیرد و موقعیت عدد در آرایه را برمی‌گرداند. در اینجا، یک آرایه مرتب از اعداد 1 تا 10 ایجاد شده است و سپس عدد 6 در این آرایه جستجو شده و نتیجه گزارش می‌شود.