کامپیوترهابرنامه نویسی

جستجوی باینری یکی از ساده ترین راه ها برای یافتن یک عنصر در یک آرایه است

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

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

بنابراین، اصل این روش چیست؟ بلافاصله ارزشمند است بگویم که جستجو باینری در هر آرایه کار نمی کند، بلکه فقط در مجموعه ای از اعداد مرتب شده است. در هر مرحله بعد، عنصر میانگین آرایه گرفته می شود (به شماره عنصر اشاره دارد). اگر تعداد مورد نظر بیشتر از میانگین باشد، همه چیز که در سمت چپ است، یعنی کمتر از عنصر متوسط است، می تواند از بین برود و در آنجا جستجو نشود. برعکس، اگر کمتر از میانگین باشد، در میان عدد در سمت راست، شما نمیتوانید آنها را جستجو کنید. بعد، ما یک منطقه جستجو جدید را انتخاب می کنیم، جایی که عنصر اول عنصر میانی کل آرایه است، و آخرین عنصر باقی خواهد ماند. میانگین عدد ناحیه جدید، ¼ کل قسمت است، یعنی (آخرین عنصر + عنصر میانگین آرایه کل) / 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 بیش از 10 است، ما 7 را رد می کنیم. فقط 10، 12 و 18 باقی مانده اند.

در اینجا عنصر میانی در حال حاضر 12 است، این تعداد مورد نیاز است. وظیفه تکمیل شده است - شماره 12 یافت می شود.

Similar articles

 

 

 

 

Trending Now

 

 

 

 

Newest

Copyright © 2018 fa.atomiyme.com. Theme powered by WordPress.