الگوریتم‌های جست‌وجو؛ چطور سریع‌تر به جواب برسیم؟

مقدمه

فرض کن یک لیست شامل یک میلیون عدد داری و می‌خوای یک عدد مشخص رو داخلش پیدا کنی. اولین راهی که به ذهنت می‌رسه چیه؟

احتمالاً از اول لیست شروع می‌کنی و تک‌تک اعداد رو بررسی می‌کنی تا به عدد موردنظرت برسی.

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

اینجاست که الگوریتم‌های جست‌وجو اهمیت پیدا می‌کنن.

در این مقاله، دو الگوریتم معروف جست‌وجو رو بررسی می‌کنیم: جست‌وجوی خطی (Linear Search) و جست‌وجوی دودویی (Binary Search).

۱. جست‌وجوی خطی چیست؟

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

فرض کن لیست زیر رو داریم:

numbers = [12, 7, 25, 4, 18, 30]

می‌خوایم عدد 18 رو پیدا کنیم. الگوریتم از ابتدای لیست شروع می‌کنه:

1. عدد ۱۲ رو بررسی می‌کنه.
2. عدد ۷ رو بررسی می‌کنه.
3. عدد ۲۵ رو بررسی می‌کنه.
4. عدد ۴ رو بررسی می‌کنه.
5. به عدد ۱۸ می‌رسه و جست‌وجو رو متوقف می‌کنه.

پیاده‌سازی این الگوریتم در پایتون ساده‌ست:

def linear_search(numbers, target):
    for index, number in enumerate(numbers):
        if number == target:
            return index

    return -1


numbers = [12, 7, 25, 4, 18, 30]

result = linear_search(numbers, 18)

print(result)

خروجی:

4

چون عدد ۱۸ در اندیس ۴ قرار داره.

اگر عنصر موردنظر در لیست وجود نداشته باشه، تابع مقدار -1 رو برمی‌گردونه.

پیچیدگی زمانی جست‌وجوی خطی

در بدترین حالت، ممکنه مجبور بشیم تمام عناصر لیست رو بررسی کنیم.

اگر تعداد عناصر رو با n نشون بدیم، پیچیدگی زمانی این الگوریتم در بدترین حالت برابر با O(n) هست.

یعنی با افزایش تعداد عناصر، تعداد عملیات موردنیاز هم می‌تونه به‌صورت خطی افزایش پیدا کنه.

۲. جست‌وجوی دودویی چیست؟

حالا تصور کن لیست ما مرتب شده باشه.

به‌جای اینکه عناصر رو یکی‌یکی بررسی کنیم، می‌تونیم هر بار به وسط لیست نگاه کنیم و بر اساس نتیجه، نیمی از محدوده جست‌وجو رو کنار بذاریم.

به این روش جست‌وجوی دودویی (Binary Search) می‌گن.

برای مثال، لیست زیر رو در نظر بگیر:

numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56]

می‌خوایم عدد 23 رو پیدا کنیم.

الگوریتم چطور کار می‌کنه؟

مرحله اول: عنصر وسط لیست رو بررسی می‌کنیم. عدد وسط 16 هست. چون ۲۳ از ۱۶ بزرگ‌تره، می‌دونیم که اگر عدد موردنظر وجود داشته باشه، باید در سمت راست قرار گرفته باشه. پس نیمه چپ رو کنار می‌ذاریم.

مرحله دوم: وسط محدوده باقی‌مونده رو بررسی می‌کنیم. در این مرحله به عدد 38 می‌رسیم. چون ۲۳ از ۳۸ کوچک‌تره، محدوده جست‌وجو به سمت چپ برمی‌گرده.

مرحله سوم: عدد ۲۳ رو پیدا می‌کنیم و جست‌وجو به پایان می‌رسه.

نکته مهم اینه که در هر مرحله، بخش بزرگی از عناصر رو بدون بررسی مستقیم کنار گذاشتیم.

۳. پیاده‌سازی جست‌وجوی دودویی با پایتون

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

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2

        if numbers[middle] == target:
            return middle

        elif numbers[middle] < target:
            left = middle + 1

        else:
            right = middle - 1

    return -1


numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56]

result = binary_search(numbers, 23)

print(result)

خروجی:

5

عدد ۲۳ در اندیس ۵ قرار داره.

کد دقیقاً چه کاری انجام می‌ده؟

• `left` ابتدای محدوده جست‌وجو رو مشخص می‌کنه.
• `right` انتهای محدوده رو مشخص می‌کنه.
• `middle` اندیس عنصر وسط محدوده‌ست.
• اگر عنصر وسط با عدد موردنظر برابر باشه، اندیس اون برگردونده می‌شه.
• اگر عنصر وسط کوچک‌تر از عدد موردنظر باشه، جست‌وجو به سمت راست ادامه پیدا می‌کنه.
• در غیر این صورت، محدوده جست‌وجو به سمت چپ منتقل می‌شه.

اگر left از right بزرگ‌تر بشه، یعنی محدوده‌ای برای بررسی باقی نمونده و عنصر موردنظر پیدا نشده.

> نکته مهم: جست‌وجوی دودویی فقط زمانی به‌درستی کار می‌کنه که داده‌ها مرتب باشن.

۴. تفاوت پیچیدگی زمانی این دو الگوریتم

حالا سؤال اصلی اینه: کدوم الگوریتم سریع‌تره؟

پاسخ به شرایط مسئله بستگی داره، اما برای مجموعه‌های بزرگ و مرتب، جست‌وجوی دودویی معمولاً انتخاب بسیار بهتریه.

مقایسه دو الگوریتم

جست‌وجوی خطی:

• نیاز به داده مرتب: خیر
• بهترین حالت: `O(1)`
• بدترین حالت: `O(n)`
• مناسب برای داده‌های کوچک و نامرتب: بله
• مناسب برای داده‌های بزرگ و مرتب: گاهی

جست‌وجوی دودویی:

• نیاز به داده مرتب: بله
• بهترین حالت: `O(1)`
• بدترین حالت: `O(log n)`
• مناسب برای داده‌های کوچک و نامرتب: خیر
• مناسب برای داده‌های بزرگ و مرتب: معمولاً بله

برای اینکه تفاوت رو بهتر درک کنی، یک مجموعه با یک میلیون عنصر رو در نظر بگیر.

در جست‌وجوی خطی، در بدترین حالت ممکنه یک میلیون عنصر بررسی بشه.

اما در جست‌وجوی دودویی، با هر مرحله تعداد عناصر باقی‌مونده تقریباً به نصف کاهش پیدا می‌کنه. برای یک میلیون عنصر، حداکثر حدود ۲۰ مرحله برای پیدا کردن یک عنصر لازم داریم.

این تفاوت یکی از دلایل مهم یادگیری الگوریتم‌ها در مهندسی نرم‌افزاره.

۵. آیا جست‌وجوی دودویی همیشه بهتره؟

نه.

اگر فقط چند عنصر داشته باشیم، جست‌وجوی خطی ممکنه ساده‌تر و کاملاً کافی باشه.

از طرف دیگه، اگر داده‌ها مرتب نباشن، ممکنه مجبور بشیم ابتدا اون‌ها رو مرتب کنیم. این فرایند هزینه زمانی خودش رو داره.

همچنین اگر داده‌ها دائماً تغییر کنن، هزینه مرتب نگه داشتن اون‌ها هم باید در نظر گرفته بشه.

بنابراین، انتخاب الگوریتم مناسب فقط به پیچیدگی زمانی اون محدود نمی‌شه؛ شرایط واقعی مسئله هم اهمیت داره.

یک برنامه‌نویس خوب کسی نیست که همیشه از پیچیده‌ترین الگوریتم استفاده کنه، بلکه کسیه که با توجه به نیاز پروژه، راه‌حل مناسب رو انتخاب می‌کنه.

۶. یک چالش برای تو

حالا که با هر دو الگوریتم آشنا شدی، وقتشه خودت رو محک بزنی.

تابعی بنویس که یک لیست مرتب و یک عدد هدف دریافت کنه و با استفاده از جست‌وجوی دودویی، اندیس اون عدد رو برگردونه.

شرایط:

• اگر عدد پیدا شد، اندیس اون رو برگردون.
• اگر عدد وجود نداشت، مقدار `-1` رو برگردون.
• از حلقه `while` استفاده کن.
• از عملگر `in` برای پیدا کردن عدد استفاده نکن.

مثال:

numbers = [3, 9, 14, 21, 28, 35, 42]

print(binary_search(numbers, 21))
print(binary_search(numbers, 10))

خروجی مورد انتظار:

3
-1

جمع‌بندی

الگوریتم‌های جست‌وجو از مفاهیم پایه‌ای اما مهم علوم کامپیوتر هستن.

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

یادگیری این مفاهیم فقط برای حل تمرین‌های دانشگاهی یا مسابقات برنامه‌نویسی نیست. این دانش بهت کمک می‌کنه هنگام طراحی نرم‌افزار، درباره عملکرد، مقیاس‌پذیری و هزینه محاسباتی تصمیم‌های بهتری بگیری.

در برنامه‌نویسی، مهم نیست فقط به جواب برسی؛ مهمه بدونی چطور می‌تونی به شکل بهتری به اون جواب برسی.

Xorix Academy | یادگیری برنامه‌نویسی، از پایه تا پیشرفته