Unul dintre cei mai fundamentali algoritmi din informatică este algoritmul de căutare binară. Puteți implementa Căutarea binară folosind două metode: metoda iterativă și metoda recursivă. În timp ce ambele metode au aceeași complexitate în timp, metoda iterativă este mult mai eficientă în ceea ce privește complexitatea spațiului.

Metoda iterativă are o complexitate spațială de O(1) în comparație cu O(logn) produs prin metoda recursivă. Deci, cum puteți implementa algoritmul de căutare binară folosind metoda iterativă în C, C++ și Python?

Ce este căutarea binară?

Căutarea binară, cunoscută și sub denumirea de căutare la jumătate de interval, căutare logaritmică sau binary chop, este un algoritm care caută și returnează poziția unui element într-o matrice sortată. Elementul de căutare este comparat cu elementul din mijloc. Luând media limitelor inferioare și superioare, puteți găsi elementele de mijloc.

Dacă elementul de căutare este mai mare decât elementul din mijloc, înseamnă că toate elementele din partea stângă sunt mai mici decât elementul de căutare. Deci, controlul se deplasează în partea dreaptă a matricei (dacă matricea este în ordine crescătoare) prin creșterea limitei inferioare la următoarea poziție a elementului din mijloc.

instagram viewer

În mod similar, dacă elementul de căutare este mai mic decât elementul din mijloc, înseamnă că toate elementele din partea dreaptă sunt mai mari decât elementul de căutare. Deci, controlul se deplasează în partea stângă a matricei prin schimbarea limitei superioare la poziția anterioară a elementului din mijloc.

Acest lucru reduce drastic numărul de comparații în comparație cu implementarea căutării liniare acolo unde numărul de comparații este egal cu numărul de elemente în cel mai rău caz. Această metodă se dovedește foarte utilă pentru a găsi numere într-o agendă sau cuvinte într-un dicționar.

Iată o reprezentare schematică a Algoritmul de căutare binar:

Căutare binară folosind C

Urmați acești pași pentru a implementa Căutarea binară folosind C:

Întregul cod sursă al programului de căutare binar folosind C, C++, Java și Python este prezent în acesta Depozitul GitHub.

Programul definește o funcție, binarySearch(), care returnează fie indexul valorii găsite, fie -1 daca nu este prezent:

#include <stdio.h>
intbinarySearch(int arr[], int arr_size, int search_number){
/*... */
}

Funcția funcționează prin restrângerea iterativă a spațiului de căutare. Deoarece căutarea binară funcționează pe matrice sortate, puteți calcula mijlocul care altfel nu are sens. Puteți fie să cereți utilizatorului o matrice sortată, fie să utilizați algoritmi de sortare precum Bubble sau Selection sort.

The scăzut și înalt variabilele stochează indecșii care reprezintă limitele spațiului curent de căutare. mijlocul stochează indexul în mijloc:

int scăzut = 0, mare = arr_size - 1, mijlocul;

Principalul in timp ce() bucla va restrânge spațiul de căutare. Dacă valoarea indexului scăzut devine vreodată mai mare decât indicele ridicat, atunci spațiul de căutare a fost epuizat, astfel încât valoarea nu poate fi prezentă.

in timp ce (scăzut <= ridicat) {
/* continuă... [1] */
 }
întoarcere-1;

După actualizarea punctului de mijloc la începutul buclei, există trei rezultate posibile:

  1. Dacă valoarea de la mijloc este cea pe care o căutăm, returnați acel indice.
  2. Dacă valoarea punctului de mijloc este mai mare decât cea pe care o căutăm, reduceți valoarea maximă.
  3. Dacă valoarea punctului de mijloc este mai mică, creșteți valoarea scăzută. 
/* [1] ...continuare */
 mijloc = (scăzut + (înalt - scăzut)) / 2;
dacă (arr[mid] == search_number)
întoarcere mijlocul;
altfeldacă (arr[mid] > search_number)
 ridicat = mijloc - 1;
altfel
 scăzut = mijloc + 1;

Testați funcția cu intrarea utilizatorului. Utilizare scanf() pentru a obține intrare din linia de comandă, inclusiv dimensiunea matricei, conținutul acesteia și un număr de căutat:

intprincipal(){
int arr[100], i, arr_size, search_number;
 printf("Introduceți numărul de elemente: ");
 scanf("%d", &arr_size);
 printf("Vă rugăm să introduceți numerele: ");
pentru (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Introduceți numărul de căutat: ");
 scanf("%d", &număr_căutare);


i = binarySearch (arr, arr_size, search_number);


dacă (i==-1)
 printf("Numărul nu este prezent");
altfel
 printf("Numărul este prezent la poziția %d", i + 1);
întoarcere0;
}

Dacă găsiți numărul, afișați poziția sau indexul acestuia, în caz contrar un mesaj care spune că numărul nu este prezent.

Căutare binară folosind C++

Puteți converti programul C într-un program C++ importând fișierul Flux de intrare ieșire și utilizați namespace std pentru a evita repetarea de mai multe ori pe parcursul programului.

#include <iostream>
folosind spatiu de numestd;

Utilizare cout cu operator de extractie << în loc de printf() și cin cu operator de inserare >> în loc de scanf() iar programul dvs. C++ este gata.

printf("Introduceți numărul de elemente: ");
cout <<"Introduceți numărul de elemente: ";
scanf("%d", &arr_size);
cin >> arr_size;

Căutare binară folosind Python

Deoarece Python nu are suport încorporat pentru matrice, utilizați liste. Definiți o funcție, binarySearch(), care acceptă trei parametri, lista, dimensiunea acesteia și un număr de căutat:

defbinarySearch(arr, arr_size, search_number):
 scăzut = 0
 mare = arr_size - 1
in timp ce scăzut <= ridicat:
 mijloc = scăzut + (înalt-jos)//2
 if arr[mid] == search_number:
întoarcere mijlocul
elif arr[mid] > search_number:
 ridicat = mijloc - 1
altfel:
 scăzut = mijloc + 1
întoarcere-1

Inițializați două variabile, scăzut și înalt, pentru a servi drept limită inferioară și superioară a listei. Similar implementării C, utilizați a in timp ce buclă care restrânge spațiul de căutare. Inițializați mijlocul pentru a stoca valoarea de mijloc a listei. Python furnizează operatorul de diviziune de etaj(//) care oferă cel mai mare număr întreg posibil.

Faceți comparații și restrângeți spațiul de căutare până când valoarea medie este egală cu numărul de căutare. Dacă numărul de căutare nu este prezent, controlul va reveni -1.

arr_size = int (input("Introduceți numărul de elemente: "))
arr=[]
imprimare("Vă rugăm să introduceți numerele: ", sfârşitul="")
pentru i în interval (0,arr_size):
 arr.append(int(intrare()))
search_number = int (input("Introduceți numărul de căutat: "))
rezultat = binarySearch (arr, arr_size, search_number)
dacă rezultat == -1:
 imprimare("Numărul nu este prezent")
altfel:
 print("Număr este prezent la poziție ", (rezultat + 1))

Testați funcția cu intrarea utilizatorului. Utilizare intrare() pentru a obține dimensiunea listei, conținutul acesteia și un număr de căutat. Utilizare int() pentru a tipări intrarea șirului acceptată de Python ca implicit într-un număr întreg. Pentru a adăuga numere la listă, utilizați adăuga() funcţie.

Apel binarySearch() și transmiteți argumentele. Dacă găsiți numărul, afișați poziția sau indexul acestuia, în caz contrar un mesaj care spune că numărul nu este prezent.

Ieșirea algoritmului de căutare binar

Următoarea este rezultatul algoritmului de căutare binară când elementul este prezent în matrice:

Următoarea este rezultatul algoritmului de căutare binară când elementul nu este prezent în matrice:

Aflați structurile și algoritmii fundamentale de date

Căutarea este unul dintre primii algoritmi pe care îi înveți și sunt adesea solicitați în concursuri de codare, plasamente și interviuri. Alți algoritmi pe care ar trebui să-i înveți sunt sortarea, hashingul, programarea dinamică, potrivirea șirurilor și algoritmii de testare a primarității.

În plus, este esențial să înțelegem complexitatea în timp și spațiu a algoritmilor. Ele sunt unul dintre cele mai cruciale concepte din informatică în determinarea eficienței oricărui algoritm. Cu cunoștințe despre Structuri de Date și Algoritmi, sunteți obligat să construiți cele mai bune programe.