Nyelv :
SWEWE Tag :Bejelentkezés |Bejegyzés
Keresés
Enciklopédia közösség |Enciklopédia válaszok |Küldje el kérdését |Szókincs |Feltöltés ismeretek
Előző 1 Következő Válassza ki a Pages

Bináris keresés

Bináris keresés, más néven bináris keresés, az az előnye, viszonylag kevesebb, a keresési sebesség, jó átlagos teljesítményt, hátránya szükséges 0.059194 rendezett asztal, és helyezze törlése nehézségeket. Ezért a bináris keresési módszer alkalmazható nem gyakran gyakori változások egy rendezett lista. Először is, azt feltételezik, hogy a táblázat alapján emelkedő sorrendben Elemek az asztal közepére, és keresse meg a kulcsszavakat felvett viszonylag kulcsszó, ha a kettő megegyezik, akkor megtalálja a siker, különben használni az asztal közepére a felvétel előtt és után a két al-asztal, ha közepén felvétel több, mint megtalálni a kulcsszavakat kulcsszavakat, hogy megtalálja tovább, mielőtt a gyermek asztal, különben a gyermek után további keresési tábla. Ismételje meg a folyamatot, amíg meg nem találja a rekordok megfelelnek a feltételeknek, a keresés sikeres, vagy addig, amíg a gyerek tábla nem létezik, amely időpontban keresés sikertelen.Bevezetés az algoritmusok

Algoritmus igényel

Szekvenciális tárolási struktúra kell használni

2. meg kell rendelni kulcsszó méretét.

Összetettsége az algoritmus

Feltéve, hogy a tömb n hosszúságú, az algoritmus bonyolultsága O (log (n))

Íme néhány pszeudo-kód bináris keresés:

BinarySearch (max, min, des)

közép-<(max min) / 2

while (min <= max)

mid = (min max) / 2

ha mid = des majd

vissza közepén

elseif közepétől> des akkor

max = mid-1

más

min = közepes 1

vissza max

Binary keresési módszer, más néven bináris keresési módszer, amely teljes mértékben kihasználja közötti kapcsolat elemei a rend, a használata oszd meg és uralkodj stratégia, a legrosszabb esetben befejezi a keresést feladatot O (log n). Az alapötlet az, hogy a n elemek nagyjából azonos számú két és fél, hogy a [n / 2], és szeretné megtalálni x az összehasonlítás, ha x = a [n / 2], hogy megtaláljuk x, az algoritmus véget ér. Ha x <a [n / 2], akkor csak a bal fele a tömb folyamatos keresés a x (Ez azt feltételezi, hogy a tömb elemeit mutatja be növekvő sorrendben). Ha x> a [n / 2], akkor csak folytassa jobb felét a tömb a keresési x.

Bináris keresési módszert általában BUG létezik egy kritikus értéket, vagyis nem az utolsó, hogy megtalálják, vagy az első érték. Lehet összehasonlítani az utolsó két szám, ami a végén ismét értékének meghatározásához azonos értékű, és nézd.

Kód Példa

pascal forráskód

C nyelvi kódja

Java kód

public class BinarySearch {/ *** bináris keresési algoritmus ** @ param srcArray rendelt tömb * @ param des megtalálja a tömb elem * @ return des megjelölt, és nem talált vissza -1 * / public static int binarySearch (int [] srcArray , int des) {int low = 0, int high = srcArray.length-1, míg (low <= magas) {int közepes = low ((magas-alacsony) / 2), ha (des == srcArray [közép ]) {return közép;} else if (des <srcArray [közép]) {high = közepes - 1;} else {low = közepes 1;}} return 1;} public static void main (String [] args ) {int [] src = new int [] {1, 3, 5, 7, 8, 9}; System.out.println (binarySearch (src, 3));}} AAuto kód

/ / Bináris keresés

funkció binSearch (t, v) {

var p = # t;

var p2;


Előző 1 Következő Válassza ki a Pages
Használó Felülvizsgálati
Nincs még hozzászólás
Én is kommentálom [Látogató (44.210.*.*) | Bejelentkezés ]

Nyelv :
| Ellenőrző kód :


Keresés

版权申明 | 隐私权政策 | Szerzői jog @2018 A világ enciklopédikus tudás