A számítástechnika egyik legalapvetőbb algoritmusa a bináris keresési algoritmus. A bináris keresés két módszerrel valósítható meg: az iteratív módszerrel és a rekurzív módszerrel. Bár mindkét módszer időbonyolítása azonos, az iteratív módszer sokkal hatékonyabb a térkomplexitás szempontjából.

Az iteratív módszer térkomplexitása: O(1) összehasonlítva O(bejelentkezés) rekurzív módszerrel állítjuk elő. Tehát hogyan valósíthatja meg a bináris keresési algoritmust az iteratív módszerrel C, C++ és Python nyelven?

Mi az a bináris keresés?

A bináris keresés, más néven félintervallum keresés, logaritmikus keresés vagy bináris vágás egy olyan algoritmus, amely megkeresi és visszaadja egy elem pozícióját egy rendezett tömbben. A keresőelemet összehasonlítja a középső elemmel. Az alsó és felső határok átlagát véve megtalálhatjuk a középső elemeket.

Ha a keresőelem nagyobb, mint a középső elem, az azt jelenti, hogy a bal oldalon lévő összes elem kisebb, mint a keresőelem. Tehát a vezérlés a tömb jobb oldalára tolódik el (ha a tömb növekvő sorrendben van), az alsó határt a középső elem következő pozíciójáig növelve.

instagram viewer

Hasonlóképpen, ha a keresőelem kisebb, mint a középső elem, az azt jelenti, hogy a jobb oldalon lévő összes elem nagyobb, mint a keresőelem. Tehát a vezérlés a tömb bal oldalára tolódik el, ha a felső határt a középső elem előző pozíciójára módosítja.

Ez drasztikusan csökkenti az összehasonlítások számát a lineáris keresés megvalósítása ahol az összehasonlítások száma megegyezik a legrosszabb forgatókönyv elemeinek számával. Ez a módszer nagyon hasznosnak bizonyul számok kereséséhez a telefonkönyvben vagy szavak kereséséhez a szótárban.

Íme egy diagramos ábrázolása a Bináris keresési algoritmus:

Bináris keresés C használatával

Kövesse az alábbi lépéseket a bináris keresés C használatával történő megvalósításához:

A C, C++, Java és Python bináris keresőprogram teljes forráskódja jelen van ebben GitHub adattár.

A program meghatároz egy függvényt, bináris keresés(), amely vagy a talált érték indexét adja vissza, vagy -1 ha nincs jelen:

#beleértve <stdio.h>
intbináris Keresés(int arr[], int arr_size, int keresési_szám){
/*... */
}

A funkció a keresési terület iteratív szűkítésével működik. Mivel a bináris keresés rendezett tömbökön működik, kiszámolhatja a közepét, aminek egyébként nincs értelme. Kérhet a felhasználótól egy rendezett tömböt, vagy használhat rendezési algoritmusokat, például buborékos vagy kijelölési rendezést.

A alacsony és magas változók tárolják azokat az indexeket, amelyek az aktuális keresési tér határait reprezentálják. középső középen tárolja az indexet:

int alacsony = 0, magas = arr_size - 1, közép;

A fő míg() ciklus leszűkíti a keresési teret. Ha az alacsony index értéke valaha nagyobb lesz, mint a magas index, akkor a keresési terület kimerült, így az érték nem lehet jelen.

míg (alacsony <= magas) {
/* folytatódik... [1] */
 }
Visszatérés-1;

Miután frissítette a felezőpontot a ciklus elején, három lehetséges kimenetel lehetséges:

  1. Ha a felezőpontban lévő érték megegyezik a keresett értékkel, akkor adja vissza ezt az indexet.
  2. Ha a középpont értéke nagyobb, mint a keresett érték, csökkentse a magas értéket.
  3. Ha a középpont értéke kisebb, növelje az alsó értéket. 
/* [1] ...folytatás */
 közép = (alacsony + (magas - alacsony)) / 2;
if (arr[mid] == keresési_szám)
Visszatérés középső;
másha (arr[közép] > keresési_szám)
 magas = közép - 1;
más
 alacsony = közép + 1;

Tesztelje a funkciót felhasználói bevitellel. Használat scanf() a parancssorból származó bevitelhez, beleértve a tömb méretét, tartalmát és a keresendő számot:

intfő-(){
int arr[100], i, arr_size, search_number;
 printf("Adja meg az elemek számát: ");
 scanf("%d", &arr_size);
 printf("Kérjük, adja meg a számokat: ");
for (i = 0; én < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Írja be a keresendő számot: ");
 scanf("%d", &keresési_szám);


i = bináris Keresés (arr, arr_size, search_number);


ha (i==-1)
 printf("Szám nincs jelen");
más
 printf("A szám a %d pozícióban található", i + 1);
Visszatérés0;
}

Ha megtalálta a számot, jelenítse meg a pozícióját vagy indexét, ellenkező esetben egy üzenet, amely szerint a szám nincs jelen.

Bináris keresés C++ használatával

A C programot C++ programmá konvertálhatja a Bemeneti kimeneti adatfolyam és névtér használata std hogy ne ismételje meg többször a program során.

#beleértve <iostream>
segítségével névtérstd;

Használat cout elszívó kezelővel << ahelyett printf() és cin beszúró operátorral >> ahelyett scanf() és kész is a C++ programod.

printf("Adja meg az elemek számát: ");
cout <<"Adja meg az elemek számát: ";
scanf("%d", &arr_size);
cin >> arr_size;

Bináris keresés Python használatával

Mivel a Python nem támogatja a tömböket, használjon listákat. Határozzon meg egy függvényt, bináris keresés(), amely három paramétert fogad el, a listát, a méretét és a keresendő számot:

defbináris Keresés(arr, arr_size, search_number):
 alacsony = 0
 magas = arr_size - 1
míg alacsony <= magas:
 közép = alacsony + (magas-alacsony)//2
 if arr[mid] == keresési_szám:
Visszatérés középső
elif arr[közép] > keresési_szám:
 magas = közép - 1
más:
 alacsony = közép + 1
Visszatérés-1

Két változó inicializálása, alacsony és magas, hogy a lista alsó és felső határaként szolgáljon. A C megvalósításhoz hasonlóan használja a míg hurok, amely leszűkíti a keresési teret. Inicializálás középső a lista középső értékének tárolásához. A Python biztosítja a padlóosztás operátort (//), amely a lehető legnagyobb egész számot adja meg.

Végezze el az összehasonlításokat, és szűkítse a keresési teret addig, amíg a középérték megegyezik a keresési számmal. Ha a keresési szám nem szerepel, a vezérlő visszatér -1.

arr_size = int (input("Adja meg az elemek számát: "))
arr=[]
nyomtatás("Kérjük, adja meg a számokat: ", vége="")
i tartományban (0,arr_size):
 arr.append(int(bemenet()))
keresési_szám = int (input("Írja be a keresendő számot: "))
eredmény = bináris keresés (arr, arr_size, search_number)
ha az eredmény == -1:
 nyomtatás("Szám nincs jelen")
más:
 print("Szám van pozícióban van jelen ", (eredmény + 1))

Tesztelje a funkciót felhasználói bevitellel. Használat bemenet() hogy megkapja a lista méretét, tartalmát és a keresendő számot. Használat int() hogy a Python által alapértelmezettként elfogadott karakterlánc-bemenetet egész számmá írja be. Ha számokat szeretne hozzáadni a listához, használja a mellékel() funkció.

Hívás bináris keresés() és adja át az érveket. Ha megtalálta a számot, jelenítse meg a pozícióját vagy indexét, ellenkező esetben egy üzenet, amely szerint a szám nincs jelen.

A bináris keresési algoritmus kimenete

A következő a bináris keresési algoritmus kimenete, ha az elem jelen van a tömbben:

A következő a bináris keresési algoritmus kimenete, ha az elem nem szerepel a tömbben:

Ismerje meg az alapvető adatstruktúrákat és algoritmusokat

A keresés az egyik első olyan algoritmus, amelyet megtanul, és gyakran felteszik rá a kérdést kódoló versenyeken, helyezéseken és interjúkon. Néhány további algoritmus, amelyet meg kell tanulnia, a rendezés, a kivonatolás, a dinamikus programozás, a karakterlánc-illesztés és a primalitástesztelési algoritmusok.

Ezenkívül elengedhetetlen az algoritmusok időbeli és térbeli összetettségének megértése. Ezek a számítástechnika egyik legfontosabb fogalmai bármely algoritmus hatékonyságának meghatározásában. Az adatstruktúrák és algoritmusok ismeretében a legjobb programokat kell elkészítenie.