Jedným z najzákladnejších algoritmov v informatike je algoritmus Binary Search. Binárne vyhľadávanie môžete implementovať pomocou dvoch metód: iteračnej metódy a rekurzívnej metódy. Zatiaľ čo obe metódy majú rovnakú časovú zložitosť, iteračná metóda je z hľadiska priestorovej zložitosti oveľa efektívnejšia.

Iteračná metóda má priestorovú zložitosť O(1) v porovnaní s O(logn) vyrobené rekurzívnou metódou. Ako teda môžete implementovať algoritmus binárneho vyhľadávania pomocou iteračnej metódy v C, C++ a Pythone?

Čo je binárne vyhľadávanie?

Binárne vyhľadávanie, tiež známe ako vyhľadávanie v polovičnom intervale, logaritmické vyhľadávanie alebo binárne štiepenie, je algoritmus, ktorý vyhľadáva a vracia polohu prvku v zoradenom poli. Prvok vyhľadávania sa porovnáva so stredným prvkom. Ak vezmeme priemer dolných a horných limitov, môžete nájsť stredné prvky.

Ak je prvok vyhľadávania väčší ako stredný prvok, znamená to, že všetky prvky na ľavej strane sú menšie ako prvok vyhľadávania. Takže ovládací prvok sa posunie na pravú stranu poľa (ak je pole vo vzostupnom poradí) zvýšením spodnej hranice na ďalšiu pozíciu stredného prvku.

instagram viewer

Podobne, ak je prvok vyhľadávania menší ako stredný prvok, znamená to, že všetky prvky na pravej strane sú väčšie ako prvok vyhľadávania. Takže ovládací prvok sa presunie do ľavej časti poľa zmenou hornej hranice na predchádzajúcu polohu stredného prvku.

To výrazne znižuje počet porovnaní v porovnaní s implementácia lineárneho vyhľadávania kde sa počet porovnaní rovná počtu prvkov v najhoršom prípade. Táto metóda je veľmi užitočná pri hľadaní čísel v telefónnom zozname alebo slov v slovníku.

Tu je schematické znázornenie Binárny vyhľadávací algoritmus:

Binárne vyhľadávanie pomocou C

Ak chcete implementovať binárne vyhľadávanie pomocou jazyka C, postupujte podľa týchto krokov:

Celý zdrojový kód Binárneho vyhľadávacieho programu pomocou C, C++, Java a Python je prítomný v tomto úložisko GitHub.

Program definuje funkciu, binárne vyhľadávanie (), ktorý vráti buď index nájdenej hodnoty alebo -1 ak nie je prítomný:

#include <stdio.h>
intbinárne vyhľadávanie(int arr[], int arr_size, int číslo_hľadania){
/*... */
}

Funkcia funguje tak, že sa opakovane zužuje vyhľadávací priestor. Keďže binárne vyhľadávanie funguje na triedených poliach, môžete vypočítať stred, ktorý inak nedáva zmysel. Môžete buď požiadať používateľa o triedené pole alebo použiť triediace algoritmy, ako je Bubble alebo Selection sort.

The nízka a vysoká premenné ukladajú indexy, ktoré predstavujú hranice aktuálneho vyhľadávacieho priestoru. stred uloží index do stredu:

int nízka = 0, vysoká = arr_size - 1, stred;

Hlavný zatiaľ čo() slučka zúži priestor vyhľadávania. Ak sa hodnota nízkeho indexu niekedy stane vyššou ako horná hodnota indexu, potom je priestor vyhľadávania vyčerpaný, takže hodnota nemôže byť prítomná.

zatiaľ čo (nízka <= vysoká) {
/* pokračuje... [1] */
 }
vrátiť-1;

Po aktualizácii stredného bodu na začiatku cyklu existujú tri možné výsledky:

  1. Ak je hodnota v strede tá, ktorú hľadáme, vráťte tento index.
  2. Ak je stredná hodnota väčšia ako tá, ktorú hľadáme, znížte vysokú.
  3. Ak je stredná hodnota menšia, zvýšte nízku. 
/* [1] ...pokračovanie */
 stred = (nízky + (vysoký - nízky)) / 2;
if (arr[mid] == search_number)
vrátiť stredný;
inakak (arr[mid] > search_number)
 vysoká = stredná - 1;
inak
 nízka = stredná + 1;

Otestujte funkciu pomocou používateľského vstupu. Použite scanf() získať vstup z príkazového riadku vrátane veľkosti poľa, jeho obsahu a čísla, ktoré sa má vyhľadať:

intHlavná(){
int arr[100], i, arr_size, search_number;
 printf("Zadajte počet prvkov: ");
 scanf("%d", &arr_size);
 printf("Zadajte čísla: ");
pre (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Zadajte číslo, ktoré chcete vyhľadať: ");
 scanf("%d", &číslo_hľadania);


i = binarySearch (arr, arr_size, search_number);


ak (i==-1)
 printf("Číslo nie je k dispozícii");
inak
 printf("Číslo sa nachádza na pozícii %d"i + 1);
vrátiť0;
}

Ak číslo nájdete, zobrazte jeho pozíciu alebo index, inak sa zobrazí hlásenie, že číslo nie je prítomné.

Binárne vyhľadávanie pomocou C++

Program C môžete previesť na program C++ importovaním súboru Vstupný výstupný tok a použite menný priestor std aby ste sa vyhli opakovaniu počas programu.

#include <iostream>
použitím menný priestorstd;

Použite cout s operátorom extrakcie << namiesto printf() a cin s operátorom vkladania >> namiesto scanf() a váš program v C++ je pripravený.

printf("Zadajte počet prvkov: ");
cout <<"Zadajte počet prvkov: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binárne vyhľadávanie pomocou Pythonu

Keďže Python nemá vstavanú podporu pre polia, použite zoznamy. Definujte funkciu, binárne vyhľadávanie (), ktorý akceptuje tri parametre, zoznam, jeho veľkosť a číslo na vyhľadávanie:

defbinárne vyhľadávanie(arr, arr_size, search_number):
 nízka = 0
 high = arr_size - 1
zatiaľ čo nízka <= vysoká:
 stred = nízky + (vysoký-nízky)//2
 if arr[mid] == search_number:
vrátiť stred
elif arr[mid] > search_number:
 vysoká = stredná - 1
inak:
 nízka = stredná + 1
vrátiť-1

Inicializujte dve premenné, nízka a vysoká, ktorý slúži ako spodná a horná hranica zoznamu. Podobne ako pri implementácii C použite a zatiaľ čo slučka, ktorá zužuje priestor vyhľadávania. Inicializovať stred na uloženie strednej hodnoty zoznamu. Python poskytuje operátor delenia podlahy (//), ktorý poskytuje najväčšie možné celé číslo.

Vykonajte porovnania a zužujte priestor vyhľadávania, kým sa stredná hodnota nerovná vyhľadávaciemu číslu. Ak vyhľadávacie číslo nie je k dispozícii, ovládací prvok sa vráti -1.

arr_size = int (vstup("Zadajte počet prvkov: "))
arr=[]
vytlačiť ("Zadajte čísla: ", koniec ="")
pre i v rozsahu (0, arr_size):
 arr.append(int(vstup()))
číslo_hľadania = int (vstup("Zadajte číslo, ktoré chcete vyhľadať: "))
výsledok = binarySearch (arr, arr_size, search_number)
ak výsledok == -1:
 vytlačiť ("Číslo nie je k dispozícii")
inak:
 vytlačiť ("Číslo je prítomný na pozícii ", (výsledok + 1))

Otestujte funkciu pomocou používateľského vstupu. Použite vstup() aby ste získali veľkosť zoznamu, jeho obsah a číslo, ktoré chcete vyhľadať. Použite int() na pretypovanie vstupu reťazca, ktorý Python akceptuje ako predvolený, na celé číslo. Ak chcete pridať čísla do zoznamu, použite pripojiť () funkciu.

Zavolajte binárne vyhľadávanie () a odovzdať argumenty. Ak číslo nájdete, zobrazte jeho pozíciu alebo index, inak sa zobrazí hlásenie, že číslo nie je prítomné.

Výstup binárneho vyhľadávacieho algoritmu

Nasleduje výstup algoritmu binárneho vyhľadávania, keď je prvok prítomný v poli:

Nasleduje výstup algoritmu binárneho vyhľadávania, keď prvok nie je prítomný v poli:

Naučte sa základné dátové štruktúry a algoritmy

Vyhľadávanie je jedným z prvých algoritmov, ktoré sa naučíte, a často sa naň pýtate v súťažiach v kódovaní, pri umiestňovaní a pohovoroch. Niektoré ďalšie algoritmy, ktoré by ste sa mali naučiť, sú triedenie, hashovanie, dynamické programovanie, porovnávanie reťazcov a algoritmy testovania primality.

Okrem toho je nevyhnutné porozumieť časovej a priestorovej zložitosti algoritmov. Sú jedným z najdôležitejších konceptov v informatike pri určovaní účinnosti akéhokoľvek algoritmu. So znalosťou dátových štruktúr a algoritmov ste povinní vytvoriť tie najlepšie programy.