Екілік іздеу - массив элементті табу үшін ең оңай жолдарының бірі

Жиі, бағдарламашылар, тіпті бастауыш, нақты нөмірін табу керек сандар жиынтығы бар екендігіне тап. Бұл жинау жиым деп аталады. Ал оған элементтерді табу үшін, жолдары көптеген бар. Бірақ олардың көпшілігі қарапайым оң жағында екілік іздеу қарастыруға болады. Бұл әдіс дегеніміз не болып табылады? Және қалай екілік іздеу жүзеге асыру? Паскаль осындай бағдарламаның ұйымдастыру үшін ең оңай ортасы болып табылады, сондықтан біз оқуға оны пайдалануға болады.

Біріншіден, бұл әдістің артықшылықтары қандай, талдау, ол сондықтан біз түсінуге болады табылады, тақырып зерттеу нүктесі қандай болып табылады. Сондықтан, кейбір табу керек, кем дегенде 100000000 элементтерін, бір өлшем бар алапты бар мүмкіндік. Әрине, бұл мәселе оңай біз циклын қолдана отырып, онда, қарапайым сызықтық іздеу арқылы шешілуі мүмкін алапта екенін барлық адамдарға қажетті элемент салыстыру болады. Мәселе осы идеяны жүзеге асыру тым көп уақыт алады, бұл. бірнеше емдеу, және негізгі мәтіннің үш желілері ішіне қарапайым Паскаль бағдарламасында, сіз оны байқамай емес, бірақ біз филиалдар үлкен саны және жақсы функционалдық бар көп немесе аз ірі жобаларды келгенде, бағдарлама тым ұзақ үшін жегіледі дайын болады. Әсіресе компьютер әлсіз өнімділігі болса. Сондықтан, кем дегенде екі есе іздеу уақытын қысқартады бинарлық іздеу, бар.

Сондықтан, осы әдістің жұмыс принципі қандай? Бірден екілік іздеу жұмыстары кез келген алапта, бірақ тек сандар сұрыпталған жиынтығы емес екенін айта кеткен жөн. әр қадамда (элементтің санын білдіреді) алаптың орта элементін қабылданған. Егер қажет болса сан артық орташа есеппен, содан кейін қалды, бұл барлық, бұл орташа ұяшықтың кем болып, алып тастауға болады және онда қарауға жоқ. Керісінше, орта есеппен кем болса - оңға сол сандардың арасында, сіз іздеу мүмкін емес. Содан кейін бірінші элементі бүкіл алаптың, және соңғы және соңғы ерік орта элементі болады, жаңа іздеу аймағын, таңдаңыз. жаңа саласындағы орташа саны барлық сегменттің ¼, яғни, (соңғы элемент + бүкіл массивтің орта элементі) / 2 болады. Тағы да, сол операция жүзеге асырылады - массивтің орташа санымен салыстыру. мақсатты мән бойынша орта көрсеткіштен кем болса, біз оң жағын қабылдамау, сондай-ақ, қазір бұл орта элементі қажетті емес еді дейін, келесі істеу.

Әрине, бұл екілік іздеу жазу қалай қарастырамыз ең жақсы болып табылады. Паскаль мұнда ешкімді сай болады - нұсқасы маңызды емес. ның қарапайым бағдарламаны жазу болсын.

Ол аты «Массив» бойынша сағ 1 жиым «niż» деп аталатын іздеу төменгі шекарасы, көрсететін айнымалы, «verh» деп аталатын жоғарғы шегі, орташа іздеу термин - «sredn»; және қажетті саны - «ИСК».

Сондықтан, алдымен, ауқымы іздеу жоғарғы және төменгі шегі тағайындау:

niż: = 1;
verh: = H + 1;

«Төменгі жоғарғы шектен аз дейін» Содан кейін циклын ұйымдастыру:

niż бастау

Әр қадамда біз сегментін 2 бөлуге:

sredn: = (niż + verh) DIV 2; {Қалған жоқ, өйткені теңсіздік, функция DIV пайдаланыңыз}

Шолудың Әр уақыт. орта қалаған болса элемент табылған болатын, өйткені, циклын тоқтату:

іf sredn = ИСК, содан кейін бұзып;

Қалаған қарағанда массив көп орта элементі болса, яғни, орташа есеппен жоғарғы шекара элемент тағайындауға, сол жағын алып тастаңыз:

егер Массив [sredn]> ИСК, содан кейін verh: = sredn;

Ал керісінше болса, ол төменгі шегара:

басқа niż: = sredn;
соңы;

Осы бағдарлама болады деп бәрі.

АҚШ-тың бұл іс жүзінде екілік әдісі көрінеді қалай қарастырайық. Осы алап қарастырайық: 1, 3, 5, 7, 10, 12, 18 және ол бірқатар 12 ұмтылатын болады.

Жалпы біз 7 элементтерін, сондықтан төртінші орта болады, мәні 7 бар.

12-ден астам, 7, 1,3 және 5 элементтері болғандықтан, біз алып тастай алады. Содан кейін біз нөмірі 4, 4/2 ешқандай қалдық Сондықтан 2. болып, жаңа элемент 10 орташа болады алдым.

12 10-ден артық болғандықтан, біз 7. тек 10, 12 және 18 болып қалады тастаңыз.

Мұнда, орта элементі қажет нөмірі болып табылады, қазірдің өзінде 12 болып табылады. Бұл міндет аяқталды - саны 12 табылды.