الگوریتم جستجوی دودویی چیست؟ + پیاده سازی در پایتون
اطلاعات، همه چیز هستند! این حرف را بیل گیتس، ایلان ماسک یا جف بزوس نزده؛ بلکه واقعیتی پنهان در دنیای امروز است. هر شخص، تیم، شرکت، سازمان یا دولتی که بتواند به خوبی از اطلاعات دردسترس خود استفاده کند، برنده خواهد بود. در برنامه نویسی، الگوریتم‌هایی ساخته شده که برای پیدا کردن اطلاعاتی خاص بین حجم زیادی از داده‌ها مورداستفاده قرار می‌گیرد. الگوریتم جستجوی دودویی یا Binary Search Algorithm، از کاربردی‌ترین الگوریتم‌های جستجو در جهان است که کاربردهای زیادی در موقعیت‌های مختلف دارد.
معرفی و تشریح جستجوی دودویی، موضوع اصلی این مطلب از وبلاگ سبزلرن است که در ادامه آن، یک نمونه الگوریتم جستجوی دودویی در پایتون را به شکل ساده پیاده‌سازی می‌کنیم.
الگوریتم جستجوی دودویی چیست؟
زمانی که قصد پیدا کردن عنصر خاصی را در یک لیست یا مجموعه‌ای از داده‌های مرتب شده داشته باشیم، الگوریتم باینری سرچ به کار خواهد آمد. این الگوریتم به جای اینکه کل لیست را از ابتدا تا انتها بررسی کرده و عنصر موردنظر را برگرداند، مستقیما لیست را به دو نیم تقسیم کرده و تا زمان پیدا شدن عنصر مدنظر، این کار را تکرار می‌کند. استفاده از این روش باعث افزایش سرعت جستجو به شکلی قابل توجه می‌شود که برای پیدا کردن یک عنصر خاص در حجم عظیمی از اطلاعات، بسیار کاربردی است.
اما استفاده از جستجوی باینری در برنامه نویسی، چه فواید و چه مشکلاتی را به همراه دارد؟ جدول زیر، برخی از مهمترین مزایا و معایب استفاده از این الگوریتم را نشان می‌دهد.
| مزایا | معایب |
|---|---|
| سرعت بالا در جستجوی داده‌ها | عدم کاربرد برای ساختارهای داده نامرتب |
| کاهش تعداد مقایسه‌ها | پیاده‌سازی پیچیده‌تر نسبت به جستجوی خطی |
| مناسب برای داده‌های بزرگ | نیاز به حافظه اضافی برای برخی پیاده‌سازی‌ها |
| مصرف کمتر منابع پردازشی | کارآمدی پایین در لیست‌های کوچک |
| کاهش زمان جستجو در داده‌های بزرگ | عدم پشتیبانی از داده‌های پویا و غیرثابت |
| کارایی در برنامه‌های Real-time | |
| پیاده‌سازی نسبتا ساده در زبان‌های مختلف |
حالا که با جوانب مثبت و منفی این الگوریتم اشنا شدیم، زمان آشنایی با کاربردها و موارد استفاده از آن رسیده است. در ادامه، می‌توانید با کارهایی که می‌توان با استفاده از یک الگوریتتم جستجوی دودویی انجام داد، اشنا شوید.
پیشنهاد دوره: اموزش پایتون
کاربرد جستجوی دودویی در برنامه نویسی
در بخش قبلی اشاره کردیم که الگوریتم Binary Search سرعت بالایی در پیدا کردن داده‌ها دارد و علاوه بر مصرف کمتر منابع پردازشی، برای جستجو در کلان داده‌ها نیز مناسب است. در نتیجه، در بسیاری از موارد که با داده‌های زیادی سروکار داریم، می‌توانیم از جستجوی دودویی استفاده کنیم.
تصویر زیر، تعداد اندکی از کاربردهای رایج این الگوریتم را نشان می‌دهد.
به صورت کلی، استفاده از الگوریتم جستجوی دودویی در زمانی مناسب است که حجم بالایی از داده‌ها را داشته باشیم و بخواهیم در سریعترین زمان ممکن، عنصر یا عناصر موردنظرمان را پیدا کنیم. همانطور که در تصویر بالا اشاره شد، جستجو در پایگاه‌های داده و استفاده در الگوریتم‌های مرتبط به تخلیل داده (Data Analyze) از جمله کاربردهای اصلی جستجوی دودویی است. از طرف دیگر، در مواردی نظیر مسیریابی در شبکه (Routing) که نیاز به پیدا کردن سریعترین مسیر وجود دارد نیز می‌توان از این الگوریتم کمک گرفت.
پیشنهاد دوره: اموزش جنگو
الگوریتم Binary Search چطور کار می‌کند؟
این الگوریتم از طریق تقسیم مداوم لیست به دو بخش کوچک‌تر، جستجو را انجام می‌دهد. بیایید با ذکر یک مثال، کارکرد جستجوی دودویی را درک کنیم.
همه ما با مفهوم بازه در ریاضی اشنا هستیم. تصور کنید بازه‌ای به این صورت داریم [1.3.5.6.7.8.11.15.20.21] و می‌خواهیم بدانیم مقدار 5 در کدام اندیس قرار گرفته است. الگوریتم باینری سرچ برای پیدا کردن پاسخ، این مراحل را طی می‌کند. اگر زمان کافی برای خواندن متن را ندارید، می‌توانید نگاهی به تصویر قرار گرفته در پایین بیندازید.
1. دریافت ورودی‌ها
ورودی ما شامل یک یا چند لیست مرتب شده و عنصر یا عناصر موردنظر است. در واقع، حتما باید این دو ورودی را به الگوریتم بدهید تا بتواند فرایند جستجو را آغاز کند. همچنین اطمینان حاصل کنید که لیست، به صورت صعودی مرتب شده باشد؛ در غیر این صورت یا با خطا مواجه می‌شوید و یا الگوریتم خروجی اشتباهی را به شما می‌دهد.
2. تعیین بازه جستجو
الگوریتم اولین عنصر که اندیس 0 را به خود اختصاص داده پیدا کرده و آن را low درنظر می‌گیرد. همچنین آخرین عنصر که بزرگترین آنها خواهد بود را به عنوان high درنظر می‌گیرد. به این ترتیب، بازه جستجو را تعیین می‌کند.
3. محاسبه عنصر میانی
در قدم بعد، مقدار low و high را با یکدیگر جمع کرده و حاصل را تقسیم بر 2 می‌کند. این مقدار، عنصر میانی لیست خواهد بود که آن را mid می‌نامیم. فرمول بدست آوردن mid به این صورت است:
Mid = (low + high) / 2
کل کار الگوریتم و جستجوی آن، براساس عنصر mid خواهد بود.
4. مقایسه عنصر میانی با مقدار هدف
در ادامه، الگوریتم عنصر موردنظر که در بخش ورودی وارد کرده بودیم را با mid مقایسه می‌کند. در اینجا، 3 حالت وجود خواهد داشت:
- اگر مقدار mid با عنصر موردنظر برابر باشد، الگوریتم خروجی را برگردانده و به اتمام می‌رسد.
- اگر مقدار mid بزرگتر از عنصر موردنظر باشد، الگوریتم نیمه کوچک‌تر (سمت چپ) بازه را به عنوان بازه جدید مدنظر قرار می‌دهد.
- اگر مقدار mid کوچک‌تر از عنصر موردنظر باشد، الگوریتم نیمه بزرگتر (سمت راست) بازه را به عنوان بازه جدید درنظر می‌گیرد.
در صورتی که حالت اول برقرار نباشد، به مرحله بعد می‌رویم.
5. تکرار مراحل 2 تا 4 تا زمان یافتن پاسخ یا اتمام لیست
در اینجا، بازه جدید تعیین شده و با تعیین مقدار low و high در بازه جدید و گرفتن میانگین آنها که همان مقدار mid باشد، جستجو ادامه پیدا می‌کند. این کار تا حدی ادامه پیدا می‌کند تا یکی از شرایط زیر برقرار شود:
- الگوریتم بعد از تکرار مراحل قبل، به عنصر موردنظر رسیده و مقدار آن را برمی‌گرداند و الگوریتم به پایان می‌رسد.
- بازه بدون پیدا کردن عنصر موردنظر به اتمام برسد که در این حالت، الگوریتم پیغام not Found یا -1 را برمی‌گرداند.
6. نمایش خروجی
در انتها، یا الگوریتم جستجوی دودویی موفق به یافتن عنصر موردنظر شده و مقدار اندیس آن را به شما نمایش می‌دهد؛ یا با به اتمام رسیدن بازه و عدم یافتن این عنصر، پیام not Found یا مقدار -1 را به شما نمایش می‌دهد.
تصویر زیر، خلاصه‌ای از مراحل گفته شده را نشان می‌دهد.
پیشنهاد مطالعه: بهترین کتابخوانه های پایتون
پیاده‌سازی الگوریتم جستجوی دودویی در پایتون
خب! به بخش جالب این مبحث رسیدیم؛ جایی که قرار است با استفاده از زبان برنامه نویسی پایتون، الگوریتم جستجوی دودویی را پیاده‌سازی کنیم. برای این کار، باید در سطح مقدماتی و بسیار مبتدی با پایتون آشنایی داشته باشید تا بتوانید مواردی مثل توابع در پایتون، آرایه‌ها، حلقه‌ها، دستورات شرطی و اصول اولیه پایتون آشنایی داشته باشید. اگر هیچگونه اشنایی با پایتون ندارید، می‌توانید از دوره رایگان آموزش مقدماتی تا پیشرفته پایتون استفاده کنید!
در غیر این صورت، بیایید کار را شروع کنیم. به این کد توجه کنید و آن را تحلیل کنید.
# Sorted list and target
numbers = [1, 3, 5, 6, 7, 8, 11, 15, 20, 21]
target = 5
# Binary search function
def binary_search(arr, target):
low = 0
high = len(arr) - 1 # Define search bounds
while low <= high:
mid = (low + high) // 2 # Find the middle
if arr[mid] == target:
return mid # Return index if found
elif arr[mid] < target:
low = mid + 1 # Search right half
else:
high = mid - 1 # Search left half
return -1 # Return -1 if not found
# Run binary search and print result
index = binary_search(numbers, target)
if index != -1:
print("The number {target} is at index ", index,".")
else:
print("The number {target} was not found.")
کد بالا، یک نمونه ساده از الگوریتم جستجوی دودویی است که برای حل کردن مثالی که در بخش قبل زدیم، استفاده می‌شود. در ابتدا، لیست یا همان بازه اولیه و عنصر هدف را به صورت دو متغیر تعریف می‌کنیم. در ادامه، یک تابع به نام binary_search تعریف کرده و در آن از دو متغیر low و high استفاده می‌کنیم. در بخش قبلی گفتیم که این دو متغیر، برای تعیین طول بازه استفاده می‌شوند.
در ادامه، یک حلقه While ایجاد می‌کنیم که حالت‌های مختلفی که بعد از مقایسه عنصر Target و مقدار mid به وجود می‌اید را با استفاده از دستورات شرطی تعریف می‌کند. به این ترتیب، توانستیم جستجوی دودویی در پایتون را پیاده‌سازی کنیم.
نکته: عبارت len در پایتون، تعداد عناصر موجود در یک آرایه را می‌شمارد؛ و از آنجایی شمارش اندیس‌ها از 0 آغاز می‌شود، با کم کردن 1 از خروجی len، می‌توان اندیس نهایی را بدست آورد.
چند تمرین برای یادگیری بهتر جستجوی دودویی در پایتون
برای اینکه بتوانید بهتر به این الگوریتم و زیروبم آن آشنا شوید، چند تمرین برای شما آماده شده که می‌توانید با پیاده‌سازی آنها، به خوبی به این الگوریتم مسلط شوید.
- الگوریتم جستجوی دودویی را برای لیست مرتب شده از رشته‌ها پیاده‌سازی کنید.
- یک لیست مرتب از اعداد فرد ایجاد کرده و 3 خروجی متفاوت از آن دریافت کنید.
- برنامه‌ای بنویسید که عنصر target را از کاربر دریافت کرده و آن را در لیست پیدا کند.
- پیدا کردن کوچک‌ترین عدد بزرگتر از عدد هدف
زمانی که تمرینات بالا را به خوبی به اتمام رساندید، تمرینات زیر که کمی پیچیده‌تر چالش برانگیز هستند را انجام دهید تا به خوبی با نحوه کار این الگوریتم و پیاده‌سازی آن به مدل‌های مختلف آشنا شوید.
- پیدا کردن تعداد دفعات استفاده از یک کلمه خاص در یک فایل متنی
- پیدا کردن نزدیک‌ترین قیمت به بودجه کاربر در فروشگاه آنلاین
- پیدا کردن عنوان کتاب در لیست عناوین مرتب شده
- نمایش اطلاعات کاربر شامل نام، سن، تاریخ تولد و شماره تلفن با استفاده از کد ملی
جمع‌بندی
روش‌های جستجوی زیادی در برنامه نویسی وجود دارند که هرکدام دارای مزایا و معایب خاص خودشان هستند. الگوریتم جستجوی دودویی، در شرایط مختلف عملکرد متفاوتی از خود نشان می‌دهد و یکی از بهترین الگوریتم‌های جستجو در برنامه نویسی محسوب می‌شود. در این مطلب سعی کردیم به شکل جامع و کاربردی، این الگوریتم را معرفی کرده و با استفاده از زبان برنامه نویسی پایتون، آن را پیاده‌سازی کنیم.
در صورتی که در انجام هرکدام از تمرینات به مشکل خوردید، می‌توانید آن را در بخش نظرات مطرح کنید!
پیشنهاد مطالعه
خیلی جامع و کامل و مفید بود دمتون گرم