Двоично търсене - анализ на алгоритъма в C ++

В разработката на софтуер навсякъде се използват масиви. "Интелигентните" типове данни в съвременните езици за програмиране, като например динамични масиви, предоставят големи възможности за удобна работа с обекти. Но алгоритмите, лежащи в основата на работата с тези типове данни, които са разработени в зората на компютърните науки - в средата на двадесети век. Първият алгоритъм за двоично търсене е публикуван през 1946 година. Разгледайте най-популярните алгоритми за работа с масиви.

Последователно търсене

Това е най-простият алгоритъм за намиране на стойност в масив. Използва метода за редуване на елементите на масива с ключова стойност. Обикновено се прави от ляво на дясно. Използва се, ако елементите в масива са малко извън списъка. Абсолютно неефективни в големи масиви, където обикновено се използват двоични търсения. Алгоритъмът работи по следния начин:


  • Сравнете стойността на ключа със стойността на елемента на масива.
  • Ако стойностите са равни, връщаме получената стойност.
  • Ако не, увеличаваме стойността на цикличната променлива с единица и сравняваме със следващия елемент на масива.
  • Индекс-последователно търсене

    По-ефективен начин за намиране на стойности в сортиран масив. Но по-взискателни за ресурси.

    Двоично търсене

    Двоичното (двоично) търсене е алгоритъм за намиране на елемент от масив чрез последователно разделяне на масив на половина и сравняване на изхода с числото от средата на масива.Ако числото от средата е по-малко от желаното, погледнем по-нататък, във втората част, ако повече - продължаваме търсенето в първата. Алгоритъмът е най-бързият от всички изброени и работи по следния начин:


  • Първо откриваме стойността на обекта в средата на масива. Проверете, за да съответства на първоначалната стойност.
  • Ако стойността от средата е по-малка от оригиналната, тогава продължаваме търсенето през втората половина, ако повече - търсим първата.
  • В получената половина продължете по същия начин: разделете я наполовина и сравнете получената стойност.
  • Търсенето се извършва, докато първоначалната стойност стане равна на стойността в масива. Ако това не се случи - тогава тази стойност в масива не съществува.
    Има няколко клопка, които могат да се срещнат при проектирането на двоично търсене.

    Препълване на избрания тип данни

    За да намерите стойността в средата на масива, трябва да направите правилните и лявите стойности и да ги разделяте на две. Това е:средата на масива = лява стойност + (лява стойност - стойност на дясно) /2

    По време на операцията по добавяне съществува опасност от препълване на типа данни. Ако масивът е толкова голям по размер, трябва да използвате различни техники, за да избегнете риска. По-долу са описани стандартни грешки при проектирането на двоични търсения.

    Грешки на стойностите

    Или грешки на единица. Много е важно да се разгледат следните възможности:

    • Празен масив.
    • Няма стойност.
    • Превишаване на масива.

    Множество копия

    Следва да се отбележи, чеВ случай на съществуване на няколко идентични екземпляра на ключ в масив, програмата трябва да намери определено (първо, последно, следващо).


    & lt; script type = "text /javascript" & gt;
    може да blockSettings2 = {blockId: "R-A-271049-5", renderTo: "yandex_rtb_R-A-70350-39", async:! 0};
    if (document.cookie.indexOf ("abmatch =") & gt; = 0) blockSettings2.statId = 70350;
    Функция (a, b, c, d, e) {a [c] = a [c] || [], a [c] .push (функция () {Ya.Context.AdvManager.render (blockSettings2)}), e = b.getElementsByTagName ("скрипт") , d = b.createElement ("скрипт"), d.type = "text /javascript", d.src = "//an.yandex .ru /system /context.js ", d.async =! 0e.parentNode.insertBefore (d, e)} (това, този.документ," yandexContextAsyncCallbacks ");

    Да разгледаме реализацията на този алгоритъм в програмния език C plus plus. Моля, обърнете внимание, че двоичното търсене работи само с подреден масив! Ако масивът не е предварително сортиран, резултатът от изчисленията ще бъде неправилен.

    Следното е код на C ++. Първоначално, първоначално се инициализира масив от цели числа arr, размер десет. След това операторът cin в цикъла изчаква въвеждането на десет стойности от потребителя (ред 10).

    В двадесетата линия програмата очаква потребителят да въведе ключовата стойност.

    Редове 29 - 35 представляват прилагания алгоритъм на двоично търсене. По време на изпълнението на програмата в средната променлива, стойността на средния елемент се записва, както следва:

    Средна стойност на масива (средата) = (лява стойност (l) + дясна стойност (r)) /2

    Ред

    arr [mid] == ключПроверява се дали средната стойност е ключовата стойност. Ако една, стойността на флага на флага се променя на TRUE, т.е. проблемът е решен. Ако средната стойност е по-голяма от стойността на нашия ключ, тогава дясната страна (променлива r) се присвоява на средата. акоНапротив, средата се поставя в r. Последният проверява флага на булев флаг.

    Предимства на двоичното търсене

    Трябва да се използва двоично търсене, ако се нуждаете от бърза работа на програмата. И да се напише такъв алгоритъм няма да навреди дори на начинаещ програмист. Но това е много важно да се вземат предвид всички екстремни случаи: извън границите на масива, липсата на желаната стойност, грешката на препълване на данни.

    Недостатъци

    За правилното функциониране на алгоритъма, масивът трябва да бъде предварително сортиран. За да направите това, можете да използвате функцията ready sort () в програмния език C ++. И още един важен момент, който трябва да се търси при изучаването на бинарно търсене в C и C ++. Този алгоритъм може да се използва само с определени структури от данни. Например, структури, които използват свързани списъци, тук не са подходящи.

    Свързани публикации