جلسهی 32: جستوجو Searching
جستوجوی خطی (linear search) را با جستوجوی دودویی (binary search) مقایسه میکنیم، هر دو نسخهی تکراری و بازگشتی آن را پیاده میکنیم و ماژول bisect را به کار میبریم.
در این جلسه یاد میگیری
- جستوجوی خطی
O(n)و دودوییO(log n)را پیاده کنید و پیششرط مرتب بودن را بشناسید. - جستوجوی دودویی را به دو شکل تکراری (
iterative) و بازگشتی (recursive) بنویسید. - از
bisect_left،bisect_rightوinsortبرای جستوجو و درج در لیست مرتب استفاده کنید. - «جستوجوی دودویی روی جواب» را برای مسائل بهینهسازی به کار ببرید.
درس
جستوجوی خطی عناصر را یکییکی بررسی میکند: 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 درست را با جستوجوی دودویی پیدا کنید.
مثالهای این جلسه
- مثال تابع در پایتون: def linear_search(items, target):
- مثال تابع در پایتون: def binary_search(nums, target):
- مثال تابع در پایتون: def search(nums, target, lo, hi):
- مثال لیست در پایتون: a = [10, 20, 20, 30]
چالشها
- Linear Search (آسان)
- Binary Search (آسان)
- Sorted Insert (آسان)
- Counting Steps (متوسط)
- Recursive Binary Search (متوسط)
- First Occurrence (متوسط)
- Grade Boundaries (متوسط)
- Count in Log Time (سخت)
- Integer Square Root (سخت)
- Shipping Capacity (سخت)
- Next Meeting (متوسط)
- Peak Finder (سخت)