الگوریتم جست و جوی باینری یا دودویی چیست؟

آیا عبارت الگوریتم سرچ باینری به گوشتان آشناست؟ تا چه حد با الگوریتم و نقش آن در سرچ آشنایی دارید؟ در این مقاله با ذکر مثال شما را با جست و جوی باینری یا دودویی آشنا می‌کنیم. قبل از همه باید با مفهوم سرچ آشنا شوید.

سرچ یا جستجو چیست؟

مفهوم سرچ، مکان اسناد، فایل‌ها، محتوای رسانه‌ای یا هر نوع داده‌ای که در پایگاه داده (دیتابیس) قرار گرفته  را در اختیار کاربر قرار می‌دهد. این سرچ از اصلی ساده پیروی می‌کند که آن هم هماهنگی معیار جستجو با اسناد موجود و نمایش آنها به کاربر است. این همان کارکرد اصلی سرچ است.

جست و جوی باینری یا دودویی چیست؟

جست و جوی باینری نوع پیشرفته‌ای از الگوریتم سرچ است که داده‌ها را از درون فهرست موارد موجود پیدا می‌کند. کار اصلی این سرچ، دونیم کردن داده‌های درون لیست تا زمان یافتن محتوای مورد نیاز و نمایش آن به کاربر در قالب نتایج جستجو است. سرچ باینری به عنوان سرچ نیم فاصله (half-interval search) یا سرچ الگوریتمی هم شناخته می‌شود.

جست و جوی باینری چگونه عمل می‌کند؟

روال کار سرچ باینری یا دودویی به شکل زیر است:

• فرایند جستجو با تعیین موقعیت مکانی عنصر میانی ردیف مرتبی از داده‌ها، آغاز می‌شود.
• سپس باید ارزش کلیدی، با این عنصر میانی مقایسه شود.
• اگر ارزش کلیدی کوچکتر از عنصر میانی باشد، پس باید مقادیر بالاتر از عنصر میانی در فرایند جستجو مورد تحلیل قرار گیرد تا عنصر هماهنگ با مقدار مدنظر پیدا شود.
• در مواردی هم که ارزش کلیدی بزرگتر از عنصر میانی است، فرایند جستجو باید مقادیر پایین‌تر از عنصر میانی را مورد مقایسه و تطبیق قرار دهد.

مثال جست و جوی باینری

شاید تابه حال از الگوریتم سرچ دودویی استفاده کرده باشید. به یافتن معنای یک لغت جدید از درون دیکشنری یا فرهنگ لغات دقت کنید. اگر به دنبال کلمه خاصی می‌گردید، لازم نیست تک تک کلمات درون کتابی قطور را به ترتیب بررسی کنید تا به آن برسید. اول به طور تصادفی نزدیک‌ترین کلمات را پیدا می‌کنید تا به کلمه مدنظر برسید. در ادامه به مثال تصویری از این نوع سرچ دقت کنید.

تصویر فوق نشان دهنده مراحل زیر است:

A.ترتیبی از 10 رقم دارید و می‌خواهید عنصر 59 را پیدا کنید.

B.ولی این ارقام با شاخص‌هایی از 0 تا 9 علامت گذاری شده‌اند. حالا باید میانه این ردیف را محاسبه کنید. برای این کار باید بالاترین مقادیر سمت راست و چپ را پیدا کرده و تقسیم بر 2 کنید. نتیجه 5/4 به دست می‌آید که آن را به سمت پایین گرد می‌کنیم و میانه 4 به دست می‌آید.

C.حالا الگوریتم، تمامی عناصر از وسط (شاخص 4) گرفته تا پایین‌تر دامنه را حذف می‌کند؛ چون عدد 59 بزرگ‌تر از 24 است. پس حالا ردیف سمت راست با 5 عنصر باقی می‌ماند.

D.حالا 59 بزرگ‌تر از 45 و کوچکتر از 63 است. میانه دامنه سمت راست هم 7 است. پس ارزش شاخص راست برابر است با میانه منهای یک که برابر با 6 می‌شود. ارزش شاخص چپ مثل قبل برابر 5 است.

E.در اینجا می دانید که عنصر 59 بعد از 45 می‌آید. از این رو شاخص چپ که 5 است به عنوان میانه هم لحاظ می‌شود.

F.این فرایند آنقدر تکرار می‌شود تا تنها یک عنصر باقی بماند یا همان عنصر مدنظر به میانه یک دامنه تبدیل شود.

مطلب پیشنهادی: الگوریتم های گوگل

مثال دوم

حالا برای شناخت عملکرد سرچ باینری به تصویر زیر دقت کنید:

A.دامنه‌ای از ارزش‌های مرتب شده از 2 تا 20 دارید و می‌خواهید 18 را پیدا کنید.

B.میانگین حدهای بالا و پایین این دامنه برابر با  4 = 2/(l + r) است. عنصر مدنظرمان بزرگتر از 4 است.

C.در فرایند جستجو، مقادیر کمتر از 4 حذف می‌شوند و مقادیر بالاتر از مقدار 4 مورد جستجو قرار می‌گیرند.

D.این فرایند تقسیم بندی آنقدر ادامه می‌یابد تا مقدار مدنظر پیدا شود.

چرا به سرچ باینری نیاز داریم؟

سرچ باینری یا دودویی به دلایل زیر به عنوان الگوریتم جستجو به کار می‌رود:

• سرچ باینری به خوبی روی داده‌های مرتب شده با هر حجم و اندازه‌ای قابل اجرا است.
• به جای اینکه به ترتیب، تک تک داده‌ها را بررسی کنید، با الگوریتم سرچ باینری به طور تصادفی داده‌ها را بررسی نموده و به عنصر مدنظر می‌رسید. با این روش، چرخه‌های جستجو کوتاه‌تر و دقیق‌تر می‌شود.
• پلتفرم‌های سرچ باینری بر اساس اصل رتبه بندی به مقایسه داده‌ها می‌پردازند و نیازی به مقایسه‌های تک به تک کندتر و نادرست نیست.
• الگوریتم سرچ، بعد از هر چرخه از جستجو، حجم دامنه داده‌ها را دو قسمت می‌کند، پس در چرخه بعدی تکرار جستجو، تنها نیمی از دامنه باقی می‌ماند.

خلاصه الگوریتم سرچ باینری یا دودویی

• کاربر با سرچ می‌تواند اسناد، فایل‌ها و سایر داده‌ها را جستجو کند. جستجوی باینری نوع پیشرفته‌ای از الگوریتم سرچ است که داده‌ها را از درون اطلاعات طبقه بندی شده پیدا می‌کند.
• جستجوی باینری تحت عنوان جستجوی نیم فاصله یا سرچ الگوریتمی هم معروف است.
• این الگوریتم ردیفی از داده‌ها را به دو نیمه تقسیم کرده و این فرایند را آنقدر تکرار می‌کند تا به عنصر مد نظر برسد.
• الگوریتم باینری، میانه هر ردیف را با تقسیم مجموع حد بالا و پایین دامنه بر دو به دست می‌آورد. حالا مقادیر بالاتر یا پایین‌تراز میانه را براساس مقدار عنصر مورد جستجو حذف می‌کند.
• این الگوریتم به طور تصادفی داده‌ها را بررسی کرده تا به عنصر مدنظر برسد. در نتیجه چرخه جستجو بسیار کوتاه‌تر و دقیق‌تر می‌شود.
• سرچ دودویی داده‌های طبقه بندی شده را بر اساس اصل طبقه بندی بررسی می‌کند و از مقایسه‌های تک به تک کند و نادرست استفاده نمی‌کند.

در نهایت . . .

الگوریتم سرچ باینری برای داده‌های نامرتب یا طبقه بندی نشده مناسب نیست. در سرچ دودویی، مقادیر مدنظر برای جستجو شدن، با عنصر میانه داده‌های مرتب شده مقایسه می‌شود تا به داده مدنظر برسید. چنین الگوریتمی علاوه بر زندگی روزمره، در دنیای علوم کامپیوتر و در حل مسائل برنامه نویسی هم مفید است.

مطلب پیشنهادی: یادگیری عمیق چیست؟

منبع

https://www.guru99.com/binary-search.html