الگوریتم جستجوی دودویی یک الگوریتم جستجو است که در یک آرایه مرتب شده با تقسیم مکرر فاصله جستجو به نصف استفاده می شود . ایده جستجوی دودویی استفاده از اطلاعاتی است که آرایه مرتب شده است و پیچیدگی زمانی را به O(log N) کاهش می دهد.
فهرست مطالب
الگوریتم جستجوی باینری چیست؟
شرایط اعمال الگوریتم جستجوی باینری در یک ساختار داده
الگوریتم جستجوی باینری
الگوریتم جستجوی باینری چگونه کار می کند؟
چگونه الگوریتم جستجوی باینری را پیاده سازی کنیم؟
الگوریتم جستجوی باینری تکراری:
الگوریتم جستجوی باینری بازگشتی:
تحلیل پیچیدگی الگوریتم جستجوی باینری
کاربردهای الگوریتم جستجوی باینری
مزایای جستجوی باینری
معایب جستجوی باینری
سوالات متداول (سؤالات متداول) در جستجوی باینری
الگوریتم جستجوی باینری چیست؟
جستجوی باینری یک الگوریتم جستجو است که برای یافتن موقعیت یک مقدار هدف در یک آرایه مرتب شده استفاده می شود . با تقسیم مکرر فاصله جستجو به نصف تا زمانی که مقدار مورد نظر پیدا شود یا فاصله زمانی خالی شود، کار می کند. فاصله جستجو با مقایسه عنصر هدف با مقدار متوسط فضای جستجو به نصف کاهش می یابد.
شرایط اعمال الگوریتم جستجوی باینری در یک ساختار داده
برای اعمال الگوریتم جستجوی باینری:
ساختار داده باید مرتب شود.
دسترسی به هر عنصر از ساختار داده باید زمان ثابتی داشته باشد.
الگوریتم جستجوی باینری
در زیر الگوریتم گام به گام برای جستجوی باینری آمده است:
با پیدا کردن شاخص میانی "mid" فضای جستجو را به دو نیمه تقسیم کنید .
عنصر میانی فضای جستجو را با کلید مقایسه کنید .
اگر کلید در عنصر میانی یافت شود، فرآیند خاتمه می یابد.
اگر کلید در عنصر میانی یافت نشد، انتخاب کنید کدام نیمه به عنوان فضای جستجوی بعدی استفاده شود.
اگر کلید کوچکتر از عنصر میانی باشد، از سمت چپ برای جستجوی بعدی استفاده می شود.
اگر کلید بزرگتر از عنصر میانی باشد، از سمت راست برای جستجوی بعدی استفاده می شود.
این روند تا زمانی که کلید پیدا شود یا کل فضای جستجو تمام شود ادامه می یابد .
الگوریتم جستجوی باینری چگونه کار می کند؟
برای درک عملکرد جستجوی دودویی، به شکل زیر توجه کنید:
آرایه ای را در نظر بگیرید [] = {2، 5، 8، 12، 16، 23، 38، 56، 72، 91} و هدف = 23 .
چگونه الگوریتم جستجوی باینری را پیاده سازی کنیم؟
الگوریتم جستجوی باینری را می توان به دو روش زیر پیاده سازی کرد
الگوریتم جستجوی باینری تکراری
الگوریتم جستجوی باینری بازگشتی
در زیر شبه کدهای رویکردها ارائه شده است.
تحلیل پیچیدگی الگوریتم جستجوی باینری
پیچیدگی زمانی:
بهترین مورد: O(1)
میانگین مورد: O (log N)
بدترین حالت: O (log N)
فضای کمکی: O(1)، اگر پشته تماس بازگشتی در نظر گرفته شود، فضای کمکی O(logN) خواهد بود.
کاربردهای الگوریتم جستجوی باینری
جستجوی دودویی می تواند به عنوان بلوک ساختمانی برای الگوریتم های پیچیده تر مورد استفاده در یادگیری ماشینی، مانند الگوریتم هایی برای آموزش شبکه های عصبی یا یافتن فراپارامترهای بهینه برای یک مدل، استفاده شود.
می توان از آن برای جستجو در گرافیک های کامپیوتری مانند الگوریتم های ردیابی پرتو یا نقشه بافت استفاده کرد.
می توان از آن برای جستجو در پایگاه داده استفاده کرد.
مزایای جستجوی باینری
جستجوی باینری سریعتر از جستجوی خطی است، به خصوص برای آرایه های بزرگ.
کارآمدتر از سایر الگوریتم‌های جستجو با پیچیدگی زمانی مشابه، مانند جستجوی درون‌یابی یا جستجوی نمایی.
جستجوی باینری برای جستجوی مجموعه داده های بزرگی که در حافظه خارجی ذخیره می شوند، مانند هارد دیسک یا در فضای ابری، مناسب است.
معایب جستجوی باینری
آرایه باید مرتب شود.
جستجوی باینری مستلزم آن است که ساختار داده مورد جستجو در مکان های حافظه پیوسته ذخیره شود.
جستجوی دودویی مستلزم آن است که عناصر آرایه قابل مقایسه باشند، به این معنی که آنها باید بتوانند مرتب شوند.
سوالات متداول (سؤالات متداول) در جستجوی باینری
1. جستجوی باینری چیست؟
جستجوی باینری یک الگوریتم کارآمد برای یافتن مقدار هدف در یک آرایه مرتب شده است. با تقسیم مکرر فاصله جستجو به نصف کار می کند.
2. جستجوی باینری چگونه کار می کند؟
جستجوی دودویی مقدار هدف را با عنصر میانی آرایه مقایسه می کند. اگر آنها برابر باشند، جستجو موفقیت آمیز است. اگر هدف کمتر از عنصر میانی باشد، جستجو در نیمه پایینی آرایه ادامه می یابد. اگر هدف بزرگتر باشد، جستجو در نیمه بالایی ادامه می یابد. این فرآیند تا زمانی که هدف پیدا شود یا فاصله جستجو خالی شود تکرار می شود.
3. پیچیدگی زمانی جستجوی باینری چقدر است؟
پیچیدگی زمانی جستجوی باینری O(log 2 n) است که n تعداد عناصر آرایه است. این به این دلیل است که اندازه فاصله جستجو در هر مرحله به نصف کاهش می یابد.
4. پیش نیازهای جستجوی باینری چیست؟
جستجوی باینری مستلزم این است که آرایه به ترتیب صعودی یا نزولی مرتب شود. اگر آرایه مرتب نشده باشد، نمی توانیم از جستجوی باینری برای جستجوی یک عنصر در آرایه استفاده کنیم.
5. اگر آرایه برای جستجوی باینری مرتب نشده باشد چه اتفاقی می افتد؟
اگر آرایه مرتب نشده باشد، جستجوی باینری ممکن است نتایج نادرستی را نشان دهد. برای تصمیم گیری در مورد اینکه کدام نیمی از آرایه جستجو شود، به ماهیت مرتب شده آرایه متکی است.
6. آیا جستجوی باینری می تواند برای داده های غیر عددی اعمال شود؟
بله، جستجوی دودویی را می توان تا زمانی که ترتیب مشخصی برای عناصر وجود داشته باشد، روی داده های غیر عددی اعمال کرد. برای مثال می توان از آن برای جستجوی رشته ها به ترتیب حروف الفبا استفاده کرد.
7. برخی از معایب رایج جستجوی باینری چیست؟
نقطه ضعف جستجوی باینری این است که آرایه ورودی باید مرتب شود تا تصمیم بگیرد که کدام نیمی از عنصر هدف می تواند قرار بگیرد. بنابراین برای آرایه های مرتب نشده، باید قبل از اعمال جستجوی باینری، آرایه را مرتب کنیم.
8. چه زمانی باید از جستجوی باینری استفاده شود؟
هنگام جستجوی یک مقدار هدف در یک آرایه مرتب شده، به خصوص زمانی که اندازه آرایه بزرگ است، باید از جستجوی باینری استفاده شود. این به ویژه برای مجموعه داده های بزرگ در مقایسه با الگوریتم های جستجوی خطی کارآمد است.
9. آیا جستجوی باینری می تواند به صورت بازگشتی پیاده سازی شود؟
بله، جستجوی باینری را می توان هم به صورت تکراری و هم به صورت بازگشتی پیاده سازی کرد. پیاده سازی بازگشتی اغلب به کد مختصرتری منجر می شود، اما ممکن است به دلیل فضای پشته بازگشتی یا فراخوانی تابع، سربار کمی بالاتر داشته باشد.
10. آیا جستجوی باینری همیشه بهترین انتخاب برای جستجو در یک آرایه مرتب شده است؟
در حالی که جستجوی دودویی برای جستجو در آرایه های مرتب شده بسیار کارآمد است، ممکن است موارد خاصی وجود داشته باشد که سایر الگوریتم های جستجو مناسب تر باشند، مانند زمانی که با مجموعه داده های کوچک سروکار داریم یا زمانی که آرایه مرتباً تغییر می کند.
