کامپیوترها, برنامه نویسی
جستجوی باینری یکی از ساده ترین راه ها برای یافتن یک عنصر در یک آرایه است
اغلب برنامهنویسان، حتی مبتدیان، با این واقعیت مواجه هستند که مجموعه ای از اعداد وجود دارد که در آن لازم است تعداد مشخصی را پیدا کنیم. این مجموعه آرایه نامیده می شود. و برای پیدا کردن عنصر مناسب در آن، راه های زیادی وجود دارد. اما ساده ترین در میان آنها جستجو باینری است. روش چیست؟ و چگونه پیاده سازی یک جستجوی باینری؟ پاسکال ساده ترین محیط برای سازماندهی چنین برنامه ای است، بنابراین ما از آن برای مطالعه استفاده خواهیم کرد.
اولا، پس از همه، مزایای این روش را تجزیه و تحلیل خواهیم کرد تا بتوانیم درک کنیم
بنابراین، اصل این روش چیست؟ بلافاصله ارزشمند است بگویم که جستجو باینری در هر آرایه کار نمی کند، بلکه فقط در مجموعه ای از اعداد مرتب شده است. در هر مرحله بعد، عنصر میانگین آرایه گرفته می شود (به شماره عنصر اشاره دارد). اگر تعداد مورد نظر بیشتر از میانگین باشد، همه چیز که در سمت چپ است، یعنی کمتر از عنصر متوسط است، می تواند از بین برود و در آنجا جستجو نشود. برعکس، اگر کمتر از میانگین باشد، در میان عدد در سمت راست، شما نمیتوانید آنها را جستجو کنید. بعد، ما یک منطقه جستجو جدید را انتخاب می کنیم، جایی که عنصر اول عنصر میانی کل آرایه است، و آخرین عنصر باقی خواهد ماند. میانگین عدد ناحیه جدید، ¼ کل قسمت است، یعنی (آخرین عنصر + عنصر میانگین آرایه کل) / 2. باز هم عملیات مشابه انجام می شود - مقایسه با میانگین تعداد آرایه. اگر مقدار دلخواه کمتر از حد متوسط باشد، سمت راست را از بین ببرید و همین کار را تا زمانی که این عنصر میانی یافت نشود.
البته، بهترین روش برای نگاه کردن به مثال، چگونگی نوشتن یک جستجوی باینری است. پاسکال در اینجا مناسب برای هر کسی است - نسخه مهم نیست. بیایید یک برنامه ساده بنویسیم
این یک آرایه از 1 تا h به نام "massiv"، متغیری است که حاوی یک مرز جستجو پایین تر است، به نام "niz"، یک مرز بالا به نام "verh"، عنصر جستجوی میان رده "sredn"؛ و تعداد مورد نیاز "ISK" است.
بنابراین، ابتدا مرزهای بالا و پایین فضای جستجو را تعیین می کنید:
Niz: = 1؛
verh: h + 1؛
سپس ما چرخه را سازماندهی میکنیم در حالی که پایین پایینتر از حد بالایی است:
در حالی که niz
در هر مرحله، بخش را به 2 قسمت تقسیم کنید:
Sredn: = (niz + verh) div 2؛ {استفاده از عملکرد div به دلیل اینکه ما باقیمانده را تقسیم می کنیم}
هر زمانی که ما یک چک را انجام می دهیم. اگر میانگین برابر با یک مورد باشد، ما چرخه را قطع می کنیم، از آنجا که عنصر مورد نظر قبلا پیدا شده است:
اگر sredn = ISK سپس شکستن؛
اگر عنصر متوسط آرایه بزرگتر از آنچه ما دنبال آن هستیم، از سمت چپ کنار می رویم، یعنی عنصر میانی را به مرز فوقانی اختصاص می دهیم:
اگر massiv [sredn]> ISK سپس verh: = sredn؛
و اگر برعکس، آن را به پایین ترین حد ممکن می رسانیم:
کاملا niz: = sredn؛
پایان
این همه چیزی است که در برنامه وجود دارد.
بیایید تحلیل کنیم که چگونه روش باینری در عمل عمل می کند. ما چنین آرایه ای را می بینیم: 1، 3، 5، 7، 10، 12، 18 و به دنبال شماره 12 در آن می گردیم.
در کل، ما 7 عنصر داریم، به طوری که میانگین آن چهارم خواهد بود، ارزش آن 7 است.
1 | 3 | 5 | 7th | 10 | 12 | 18th |
از آنجا که 12 برابر بیشتر از 7 است، عناصر 1،3 و 5 می توانند از بین بروند. بعد، ما 4 عدد سمت چپ، 4/2 بدون باقی مانده 2 است. بنابراین، عنصر متوسط جدید 10 خواهد بود.
7th | 10 | 12 | 18th |
در اینجا عنصر میانی در حال حاضر 12 است، این تعداد مورد نیاز است. وظیفه تکمیل شده است - شماره 12 یافت می شود.
Similar articles
Trending Now