هیتلر ، ناپلئون و جولیوس سزار چه ارتباطی دارند؟
همه آنها با استفاده از روش ساده و در عین حال مؤثر تقسیم و فاتح ، نبردهای اساسی را برنده شده اند.
تقسیم و فاتح همیشه یک رویکرد خارق العاده برای حل مشکلات پیچیده بوده است. این همچنین در مورد بازیابی داده ها صادق است. جستجوی باینری ، بر اساس اصل تقسیم و فاتح ، یک الگوریتم جستجوی گسترده است.
خودت آن را امتحان کن
در نظر بگیرید که می خواهید به دنبال کلمه "جستجو" در فرهنگ لغت باشید.
به طور شهودی ، شما فرهنگ لغت را در وسط باز می کنید و می بینید که آیا حرف اول صفحه پس از یا قبل از نامه آمده است.
بیایید بگوییم که نامه ای که به آن رسیدید "n" است. از آنجایی که پس از "N" در الفبای آمده است ، شما نیمه اول فرهنگ لغت را نادیده می گیرید و نیمه دوم را به دو بخش تقسیم می کنید.
حالا بگویید که به نامه "T" رسیدید.
این روند ادامه دارد تا زمانی که شما به طور شهودی به جستجوی خطی از طریق صفحات نامه "S" بروید تا این کلمه را پیدا کنید.
اکنون یک مجموعه داده بسیار بزرگتر را در نظر بگیرید. بگذارید بگوییم که می خواهید نام خود را در یک رجیستری پیدا کنید که شامل نام همه افراد جهان باشد. اگر به صورت خطی بروید ، این ممکن است ساعت ها یا حتی چند روز طول بکشد تا نام خود را پیدا کنید. با این حال ، همین کار را می توان با جستجوی باینری در بیش از 33 تکرار انجام داد.
پیش نیازهای جستجوی باینری
جستجوی باینری دارای سه پیش نیاز ساده است:
- مجموعه داده شما باید مرتب شود
- مجموعه داده شما باید مرتب شود
- مجموعه داده شما باید مرتب شود
خوب ، اکنون که یک مجموعه داده مرتب شده دارید ، اجازه دهید شروع به جستجو کنیم!
جستجوی باینری چیست؟
جستجوی باینری ، همچنین به عنوان جستجوی نیمه با فاصله ، جستجوی لگاریتمی یا باینری CHOP در علوم کامپیوتر شناخته می شود ، یک روش جستجو است که یک مقدار هدف را درون یک آرایه مرتب شده قرار می دهد. این کار را با تقسیم آرایه مرتب شده و تمرکز فقط به نیمه "مرتبط" یا "ارزشمند" و نادیده گرفتن بقیه انجام می دهد.
الگوریتم جستجو
- عنصر مورد نیاز باید با عنصر مرکز مقایسه شود.
- اگر عنصر مورد نیاز برابر با عنصر میانی باشد ، شاخص میانی را برمی گردانیم.
- در غیر این صورت اگر بزرگتر از عنصر میانی باشد ، فقط می توان بعد از عنصر میانی در نیمه زیر فرعی را یافت. در نتیجه ، ما روند را برای نیمه راست تکرار می کنیم.
- در غیر این صورت ، برای نیمه چپ تکرار کنید.
خودت آن را امتحان کن
با استفاده از این الگوریتم ، جستجوی باینری را به زبان دلخواه خود انجام دهید. ممکن است از قطعه کد در زیر کمک بگیرید. اگر اشکالی پیدا کردید ، در بخش نظرات به ما دسترسی پیدا کنید!
کد: C (اجرای بازگشتی)
خروجی: عنصر در فهرست 4 وجود دارد
کد: C ++ (اجرای تکراری)
خروجی: عنصر در فهرست 4 وجود دارد
کد: Python3 (اجرای بازگشتی)
خروجی: عنصر در فهرست 4 وجود دارد
کد: جاوا (اجرای تکراری)
خروجی: عنصر موجود در فهرست 4
تجزیه و تحلیل پیچیدگی زمانی
در حین اجرای جستجوی باینری ، عنصر هدف ممکن است در سه نوع موقعیت باشد:
- وسط آرایه (بهترین مورد)
- اولین یا آخرین عنصر آرایه (بدترین حالت)
- در هر کجا به جز موارد فوق (مورد متوسط)
بهترین پیچیدگی زمان الگوریتم جستجوی باینری o (1) است.
میانگین و بدترین پیچیدگی زمان O (log2n) است.
این پیچیدگی زمانی به طور قابل توجهی بهتر از الگوریتم جستجوی خطی است که پیچیدگی زمان متوسط و بدترین حالت O (N) است.
لمس های نهایی را به دانش خود اضافه کنید!
از آنجا که جستجوی باینری راهی سریع برای جستجو از طریق پایگاه داده های مرتب شده است ، اغلب در اشکال زدایی استفاده می شود. فرض کنید شما 100 نسخه از یک کد دارید که هر یک از آنها با دیگری متفاوت است. نسخه 1 خروجی صحیح را نشان می دهد ، اما نسخه 100 نیست.
یک روش کارآمد برای یافتن نسخه شکسته ، اجرای یک جستجوی باینری از طریق همه نسخه ها است. نسخه ها در یک سیستم کنترل نسخه به ترتیب مرتب شده وارد شده اند ، بنابراین در مورد آن نگران نباشید. کد را در نسخه 50 بررسی کنید ، آن را بسازید و ببینید که آیا این اشکال هنوز وجود دارد یا خیر.
تقسیم را ادامه دهید تا زمانی که این اشکال را معرفی کنید کشف کنید. این رویکرد کاملاً مفید است به خصوص اگر تعهدات کوچکی انجام دهید.
درک خود را آزمایش کنید
q1. با توجه به یک آرایه ورودی = و عنصر هدف = 21. تا زمان یافتن عنصر چند تکرار انجام می شود؟
Q2با توجه به یک آرایه = و عنصر هدف = 102. مقادیر میانی (عناصر آرایه مربوطه) در تکرارهای اول و دوم چیست؟
- 68 و 91
- 68 و 102
- 52 و 84
- 52 و 91
پیشرفت در الگوریتم جستجوی باینری:
تبریک! شما یاد گرفته اید که چگونه الگوریتم جستجوی باینری را پیاده سازی کنید. اما همیشه جایی برای پیشرفت وجود دارد ، درست است؟
یک راه ممکن کاهش پیچیدگی زمان بدترین حالت به O (1) است. در ابتدا ممکن است بررسی کنید که آیا عنصر هدف برابر است با اولین یا آخرین عنصر آرایه در ابتدا.
شما شگفتی های تقسیم و فاتح را کشف کرده اید و جستجوی باینری را با جزئیات کاوش کرده اید! بنابراین ، دفعه بعد که با جستجوی یک مجموعه داده بزرگ ، مانند یک فرهنگ لغت یا کمد خود روبرو می شوید ، به جای آن به بخش های آن نگاه کنید :)
قبل از ترک
جستجوی باینری اساس یک درخت جستجوی باینری را تشکیل می دهد.
اگر می خواهید در یک مقاله مشابه در مورد آن بیاموزید ، در زیر نظر خود را رها کنید و علاقه خود را به ما اطلاع دهید.
و اگر از یادگیری اصول جستجوی باینری از طریق این مقاله لذت بردید ، دانش را با برنامه نویسان و حلقه اجتماعی خود به اشتراک بگذارید. شاید شخصی در آنجا واقعاً به این منبع احتیاج داشته باشد ، و ممکن است با به اشتراک گذاشتن آن به آنها کمک کنید.
