الگوریتم جستجوی دودویی (Binary Search)

الگوریتم جستجوی دودویی یکی از پایه‌های اساسی در علوم کامپیوتر و الگوریتم‌هاست. این الگوریتم به شکل مؤثر و سریع در جستجو و یافتن عناصر در یک مجموعه‌ داده مرتب کمک می‌کند. بر اساس ایدهٔ تقسیم و حاکمیت، الگوریتم جستجوی دودویی به دسته‌ای از الگوریتم‌ها معروف به الگوریتم‌های “تقسیم و حاکم” تعلق دارد.
در الگوریتم جستجوی دودویی، از ایدهٔ تقسیم و حاکمیت برای کاهش حجم جستجو استفاده می‌شود. برای استفاده از این الگوریتم، لازم است تا داده‌ها مرتب شده باشند. این الگوریتم به صورت بازگشتی یا تکراری اقدام به تقسیم داده‌ها می‌کند و در هر مرحله به دنبال عنصر مورد نظر می‌گردد.

گام‌های اجرا:

1. تعیین میانه:

در هر مرحله، میانهٔ محتمل مجموعه داده محاسبه می‌شود. برای این منظور، اندیس ابتدایی و اندیس انتهایی مجموعه در نظر گرفته می‌شود و میانه این دو اندیس به صورت زیر محاسبه می‌شود:

2. مقایسه:

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

3. تعیین محدوده جدید:

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

4. ادامه جستجو:

با توجه به محدودهٔ جدید به صورت بازگشتی یا تکراری جستجو ادامه می‌یابد.

پیچیدگی زمانی:

الگوریتم جستجوی دودویی باعث کاهش تعداد مقایسه‌ها در هر مرحله می‌شود. پیچیدگی زمانی این الگوریتم (O(log n)) است، که در مقایسه با جستجوی خطی ((O(n))) در مجموعه‌های بزرگ بهبود قابل توجهی دارد.

در ادامه یک مثال ساده با زبان برنامه‌نویسی پایتون برای اجرای جستجوی دودویی روی یک لیست ارائه می‌دهیم:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = arr[mid]

        if mid_value == target:
            return mid  # عنصر پیدا شد
        elif mid_value < target:
            low = mid + 1  # جستجو در نیمهٔ بعدی
        else:
            high = mid - 1  # جستجو در نیمهٔ قبلی

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

# مثال
sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_element = 8

result = binary_search(sorted_list, target_element)

if result != -1:
    print(f"عنصر {target_element} در ایندکس {result} یافت شد.")
else:
    print(f"عنصر {target_element} یافت نشد.")

در این مثال، تابع binary_search یک لیست مرتب شده (sorted_list) و یک عنصر هدف (target_element) را به عنوان ورودی می‌گیرد و از الگوریتم جستجوی دودویی برای یافتن این عنصر استفاده می‌کند. سپس نتیجه جستجو به کاربر نمایش داده می‌شود. در اینجا، عنصر 8 در لیست وجود دارد و این عنصر در ایندکس 7 (از صفر شمارش) قرار دارد، بنابراین خروجی این مثال باید باشد:

عنصر 8 در ایندکس 7 یافت شد.