جستجوی باینری: سریع، دقیق، و قدرتمند 🔍⚡️جستجوی باینری (Binary Search) یکی از الگوریتم‌های اساسی و فوق‌العاده سریع برای جستجو در داده‌های مرتب‌شده است. این الگوریتم با کاهش مداوم فضای جستجو به نصف، پیچیدگی زمانی بسیار کارآمدی ارائه می‌دهد:
ایده اصلی 🧠 جستجوی باینری از اصل "تقسیم و حل" (Divide and Conquer) استفاده می‌کند:
1. لیست باید
مرتب باشد.
2. عنصر میانی لیست بررسی می‌شود:
- اگر مقدار هدف کوچک‌تر باشد، جستجو به نیمه‌ی
چپ محدود می‌شود.
- اگر مقدار هدف بزرگ‌تر باشد، جستجو به نیمه‌ی
راست محدود می‌شود.
- اگر عنصر میانی برابر مقدار هدف باشد، مکان آن پیدا شده است!
✅ مزایا 🌟 -
سرعت بالا: پیچیدگی زمانی (O(log n))، که برای داده‌های بزرگ بسیار کارآمد است.
-
مصرف کم حافظه: نیاز به فضای اضافی ندارد (به جز در نسخه بازگشتی).
-
کاربرد گسترده: در دیتابیس‌ها، موتورهای جستجو، و حتی مسائل گرافیکی.
معایب ⚠️ -
پیش‌شرط مهم: لیست باید
از پیش مرتب‌شده باشد.
- در مقایسه با
جستجوی خطی (Linear Search)، در لیست‌های کوتاه ممکن است بهینه‌تر نباشد.
- نسخه بازگشتی ممکن است در داده‌های بسیار بزرگ به دلیل استفاده از پشته دچار محدودیت شود.
پیاده‌سازی جستجوی باینری نسخه‌ی تکراری (Iterative):def binary_search_iterative(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
نسخه‌ی بازگشتی (Recursive):def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
مثال کاربردی 📚 فرض کنید لیستی از اعداد مرتب داریم:
[2, 4, 7, 10, 23, 36, 50, 72]
اگر بخواهیم عدد
23 را پیدا کنیم:
1. ابتدا عنصر میانی: (10) → مقدار هدف بزرگ‌تر است → نیمه‌ی راست.
2. عنصر میانی جدید: (36) → مقدار هدف کوچک‌تر است → نیمه‌ی چپ.
3. عنصر میانی جدید: (23) → پیدا شد!
✅ کاربردهای عملی جستجوی باینری 🔧 1.
جستجو در دیتابیس‌ها: برای پیدا کردن رکوردهای خاص.
2.
الگوریتم‌های مرتب‌سازی: مثل مرتب‌سازی ادغامی و سریع (Merge Sort, Quick Sort).
3.
حل مسائل بهینه‌سازی: پیدا کردن ریشه در توابع، جستجو در فضای جواب (Solution Space).
4.
کدنویسی رقابتی: برای حل مسائل در ساختار داده‌های مرتب.
پیچیدگی زمانی و مکانی ⏱️ -
زمانی: (O(log n)) (در بدترین، بهترین و حالت متوسط).
-
مکانی:
- نسخه‌ی تکراری: (O(1))
- نسخه‌ی بازگشتی: (O(log n))به دلیل استفاده از پشته بازگشت).
#الگوریتم 📣👨💻 @AlgorithmDesign_DataStructuer
