Bináris keresés-az algoritmus elemzése c++ - ban

Fejlesztés alatt szoftver a tömböket mindenhol használják. "Intelligens" adattípusok a modernben programozási nyelvek, , mint például a dinamikus tömbök, nagyszerű lehetőségeket kínálnak az objektumokkal való kényelmes munkavégzéshez. Az ilyen típusú adatokkal végzett munka alapjául szolgáló algoritmusokat azonban a számítástechnika hajnalán — a huszadik század közepén-fejlesztették ki. Az első bináris keresési algoritmus 1946-ban jelent meg.

Nézzük meg a legnépszerűbb algoritmusokat munkavégzéshez tömbökkel.

Szekvenciális (lineáris) keresés

Ez a legegyszerűbb algoritmus egy érték megtalálásához egy tömbben. A tömbelemek alternatív összehasonlításának módszerét használja a kulcsértékkel. Ez normálisan, balról jobbra történik. Akkor használják, ha kevés elem van a tömbben, vagy a lista nincs rendezve. Teljesen hatástalan a nagy tömbökben, ahol általában bináris keresést használnak. Az algoritmus a következőképpen működik:

• Hasonlítsa össze a legfontosabb értéket az érték a tömb elem.
• Ha az értékek egyenlőek, visszaadjuk a kapott értéket.
• Ha nem, akkor növeljük a hurokváltozó értékét eggyel, és összehasonlítjuk a tömb következő elemével.

Index-szekvenciális keresés

Egy hatékonyabb módja annak, hogy megtalálja az értéket egy rendezett tömbben. De igényesebb források.

Bináris keresés

A bináris (bináris) keresés egy algoritmus egy tömb elem megkeresésére a tömb egymás utáni felosztásával, valamint az eredeti szám összehasonlításával a tömb közepén lévő számmal. Ha a középső szám kisebb, mint amit keres, akkor a második részben tovább keresünk, ha több, akkor az elsőben folytatjuk a keresést. Az algoritmus a leggyorsabb az összes felsorolt közül, és a következőképpen működik:

• Először megtudjuk az objektum értékét a tömb közepén. Ellenőrizze, hogy megfelel-e az eredeti értéknek.
• Ha a középső érték kisebb, mint az eredeti, akkor folytatjuk a keresést a második felében, ha több, akkor az elsőben keresünk.
• Az eredményül kapott felében ugyanúgy járunk el: osztjuk fel felére és hasonlítsuk össze a kapott értéket.

A keresés addig történik, amíg a kezdeti érték megegyezik a tömb értékével. Ha ez nem történik meg, akkor a tömbben nincs megadott érték.

Számos buktatókat, hogy előfordulhat tervezése során bináris keresés.

A kiválasztott adattípus túlcsordulása

A tömb közepén lévő érték megismeréséhez össze kell adnia a jobb és a bal értékeket, és el kell osztania kettővel. Ez az:

A tömb közepe = bal érték + (bal érték-jobb érték) / 2

A hozzáadási művelet során fennáll az adattípus túlcsordulásának veszélye. Ha ilyen nagy méretű értékek vannak a tömbben, akkor különféle technikákat kell használnia a kockázat elkerülése érdekében. Az alábbiakban bemutatjuk a bináris keresés fejlesztésének standard hibáit.

Érték hibák

Vagy hibák egységenként. Nagyon fontos figyelembe venni a következő lehetőségeket:

• Üres tömb.
• Az érték hiányzik.
• A tömb határain túl.

Több példány

Figyelembe kell venni, hogy ha a kulcsnak több azonos példánya van a tömbben, akkor a programnak meg kell találnia egy bizonyos (Első, Utolsó, mellette).

Elemezzük ennek az algoritmusnak a megvalósítását a C plus plus programozási nyelven. Ne feledje, hogy a bináris keresés csak rendezett tömbökkel működik! Ha a tömb nincs előre rendezve, akkor a számítások eredménye helytelen lesz.

Az alábbiakban a C kód található ++. Először egy arr Egész változók tömbjét inicializáljuk, tízes méretű. Ezután a for hurok cin operátora tíz érték bevitelére vár a felhasználótól (tíz sor).

A huszadik sorban a program várja, hogy a felhasználó beírja a kulcs értékét.

A 29-35. sor egy megvalósított bináris keresési algoritmust képvisel. A program végrehajtása során a középső elem értékét a képlet szerint a középső változóra írják:

A tömb közepe (mid) = (bal érték (l) + jobb érték (r))/2

A húr által

arr [mid] = = kulcs

Ellenőrzi, hogy a középső érték megegyezik-e a kulcsértékkel. Ha egyenlő, akkor a flag változó értéke TRUE értékre változik, vagyis a probléma megoldódott.

Ha a középső érték nagyobb, mint a kulcsunk értéke, akkor a jobb oldali rész (r változó) középre van rendelve. Ha fordítva, akkor a mid r-be kerül.

Az utolsó a logikai változó zászló ellenőrzése.

A bináris keresés előnyei

Bináris keresést kell használni, ha a program gyors működést igényel. Még egy kezdő programozó számára sem lesz nehéz ilyen algoritmust írni. De nagyon fontos figyelembe venni az összes szélsőséges esetet: kiment a tömbből, hiányzik a kívánt érték, az adatok túlcsordulási hibája.

Hátrányok

Az algoritmus megfelelő működéséhez a tömböt előre kell rendezni. Ehhez a C++ programozási nyelven használhatja a kész rendezés () funkciót. Egy másik fontos pont, amire szüksége van figyelni, a bináris keresés tanulmányozása C-ben és C-ben++. Ez az algoritmus csak bizonyos adatstruktúrákkal használható. Például a csatolt listákat használó struktúrák itt nem működnek.