حالت آفلاین — محتوا از حافظهٔ کش نمایش داده می‌شود
آموزش الگوریتم و حل مسئله با پایتون؛ تمرین عملی

رفع خطای مرز آخر در جست‌وجوی دودویی پایتون

جست‌وجوی خطی و دودویی در پایتون؛ قرارداد و مرزها · 0٪

✍️ در این نسخه جست‌وجوی دودویی، هر دو مرز جزو محدوده‌اند: از left تا right، با احتساب هر دو خانه. وقتی مرزها برابر شوند هنوز یک نامزد داریم. بنابراین شرط ادامه باید آن حالت را هم بپذیرد. شرط اشتباه left < right گاهی همه مسیر را درست می‌رود، ولی آخرین خانه باقی‌مانده را بدون بررسی رها می‌کند.

برای مثال، در [2, 5, 11] دنبال یازده بگرد. اول خانه وسط با مقدار پنج دیده می‌شود، بعد مرز چپ به دو می‌رسد. حالا هر دو مرز دو هستند و هنوز باید همان خانه آخر را بررسی کنیم. برای یک فهرست تک‌عضوی این مشکل حتی از اولین لحظه دیده می‌شود.

کد اولیه را اصلاح کن و بازگشت شکست را بیرون حلقه نگه دار. با کوچک بودن مقدار وسط، left باید mid + 1 شود؛ با بزرگ بودن آن، right باید mid - 1 شود تا محدوده واقعاً کوچک شود. خطای رایج ترکیب مرز بسته با شرط مربوط به یک قرارداد دیگر است. این تمرین فقط فهرست صعودی با عددهای متمایز دارد؛ هنوز لازم نیست اولین رخداد تکراری را پیدا کنی.

تابع آماده course_check فقط برای ارزیابی است: تابع اصلی را صدا می‌زند و حفظ ورودی را بررسی می‌کند. آن را تغییر نده؛ پاسخ تو همان تابع خواسته‌شده است.

فعالیت شما

تابع binary_find(nums,target) روی فهرست صعودیِ عددهای صحیح متمایز، شاخص target یا -1 را برگرداند. مرزها شامل هر دو سر هستند؛ خالی -1، تک‌عضوی مطابق حضور هدف و هدف در آخرین خانه باید درست باشد. مثلاً binary_find([2,5,11],11)=2. ورودی تغییر نکند. تابع آماده course_check فقط برای ارزیابی است: تابع اصلی را صدا می‌زند و حفظ ورودی را بررسی می‌کند. آن را تغییر نده؛ پاسخ تو همان تابع خواسته‌شده است.

مطالعهٔ این گام برای همه آزاد است

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

برای انجام فعالیت وارد شوید

برای انجام فعالیت‌ها ابتدا این دوره‌های پیش‌نیاز را تکمیل کنید:

کد اولیهٔ فعالیت

def binary_find(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# این تابع آماده فقط برای ارزیابی است؛ آن را تغییر نده.
def course_check(*args):
    from copy import deepcopy
    before = deepcopy(args)
    result = binary_find(*args)
    if args != before:
        raise ValueError('ورودی نباید تغییر کند.')
    return result