جستجوی دودویی
جستجوی دودویی: الگوریتم O(log n) روی داده مرتب، پیاده‌سازی تکراری و بازگشتی و مقایسه با جستجوی خطی
جستجوی دودویی چیست؟
جستجوی دودویی (Binary Search) یکی از قدرتمندترین الگوریتم‌ها: روی داده مرتب، در هر مرحله نیمی از فضای جستجو را حذف می‌کند — مثل بازی حدس عدد!
شهود: بازی حدس عدد
عددی بین ۱ تا ۱۰۰ انتخاب شده و شما حدس می‌زنید؛ فقط پاسخ «بزرگ‌تر» یا «کوچک‌تر» می‌گیرید. بهترین استراتژی: هر بار وسط را حدس بزنید! با این روش، حداکثر ۷ حدس برای ۱۰۰ عدد کافی است (log₂ 100 ≈ 7).
الگوریتم
- low = 0 و high = آخرین اندیس
- mid = وسط بازه را محاسبه کن
- اگر عنصر mid = هدف ← پیدا شد!
- اگر عنصر mid < هدف ← برو نیمه راست (low = mid + 1)
- اگر عنصر mid > هدف ← برو نیمه چپ (high = mid − 1)
- تکرار تا low > high (پیدا نشد)
شرط حیاتی: داده باید مرتب باشد!
جستجوی دودویی روی داده نامرتب جواب غلط می‌دهد! اگر داده مرتب نیست، یا اول مرتب کنید (O(n log n)) یا از جستجوی خطی استفاده کنید.
پیچیدگی
| معیار | خطی | دودویی |
|---|---|---|
| بهترین | O(1) | O(1) |
| بدترین | O(n) | O(log n) ✓ |
| پیش‌نیاز | هیچ | داده مرتب |
| قدم برای ۱ میلیون | ۱٬۰۰۰٬۰۰۰ | ~۲۰ ✓ |
نسخه بازگشتی
همان منطق با فراخوانی خود تابع روی نیمه مناسب — الگوی تقسیم و حل (مبحث آینده).
کاربردهای واقعی
- ایندکس دیتابیس (B-Tree از همین ایده استفاده می‌کند)
- جستجو در git bisect (پیدا کردن کامیت باگ)
- تابع bisect پایتون برای درج در جای درست لیست مرتب
- debugging دودویی: نصف‌کردن کد برای پیدا کردن باگ!
نکته: خطای رایج محاسبه mid: در زبان‌هایی با int محدود، (low + high) // 2 می‌تواند سرریز کند؛ راه امن: low + (high - low) // 2 — در پایتون مشکلی نیست چون اعداد بی‌نهایت‌اند.
جمع‌بندی
- روی داده مرتب، هر مرحله نصف می‌کند ← O(log n)
- ۱ میلیون داده با فقط ~۲۰ مقایسه!
- بدون مرتب‌بودن، جواب غلط می‌دهد
- پایه ایده‌های بزرگ: BST، ایندکس دیتابیس، debugging دودویی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.