بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 32: جست‌وجو Searching

جست‌وجوی خطی (linear search) را با جست‌وجوی دودویی (binary search) مقایسه می‌کنیم، هر دو نسخه‌ی تکراری و بازگشتی آن را پیاده می‌کنیم و ماژول bisect را به کار می‌بریم.

در این جلسه یاد می‌گیری

درس

جست‌وجوی خطی عناصر را یکی‌یکی بررسی می‌کند: O(n)، ولی روی هر لیستی (حتی نامرتب) کار می‌کند. x in lst و lst.index(x) در عمل همین کار را می‌کنند.

def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

print(linear_search([7, 3, 9], 9))

جست‌وجوی دودویی روی لیست مرتب در هر گام نیمی از بازه را کنار می‌گذارد: O(log n)؛ برای یک میلیون عنصر حدود ۲۰ مقایسه. بازه را با lo و hi (شامل) نگه دارید و تا وقتی lo <= hi ادامه دهید.

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

print(binary_search([1, 4, 6, 9, 12], 9))

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

def search(nums, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search(nums, target, mid + 1, hi)
    return search(nums, target, lo, mid - 1)

ماژول bisect جست‌وجوی دودویی آماده است. bisect_left(a, x) اولین جایی است که x می‌تواند درج شود (قبل از مقادیر برابر) و bisect_right آخرین جا (بعد از برابرها). insort با حفظ ترتیب درج می‌کند (جست‌وجو O(log n)، ولی جابه‌جایی عناصر O(n)).

import bisect

a = [10, 20, 20, 30]
print(bisect.bisect_left(a, 20), bisect.bisect_right(a, 20))
bisect.insort(a, 25)
print(a)

دام‌های رایج: حلقه‌ی بی‌پایان به خاطر lo = mid به‌جای mid + 1، و اشتباه «یکی کم/زیاد» (off-by-one) در شرط < یا <=. ترفند قدرتمند: «جست‌وجوی دودویی روی جواب»؛ اگر شرطی یکنوا (monotonic) دارید (مثلاً «آیا با ظرفیت c کار تمام می‌شود؟»)، کوچک‌ترین c درست را با جست‌وجوی دودویی پیدا کنید.

مثال‌های این جلسه

چالش‌ها

  1. Linear Search (آسان)
  2. Binary Search (آسان)
  3. Sorted Insert (آسان)
  4. Counting Steps (متوسط)
  5. Recursive Binary Search (متوسط)
  6. First Occurrence (متوسط)
  7. Grade Boundaries (متوسط)
  8. Count in Log Time (سخت)
  9. Integer Square Root (سخت)
  10. Shipping Capacity (سخت)
  11. Next Meeting (متوسط)
  12. Peak Finder (سخت)

بیشتر بخوان

← جلسه‌ی 31: پیچیدگی زمانی و Big-O جلسه‌ی 33: مرتب‌سازی →