Cercetare dihotomică
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . |
| Cercetare dihotomică | |
|---|---|
 | |
| Clasă | Algoritm de căutare |
| Structură de date | Matrice |
| Cel mai rău caz din punct de vedere temporal | О (jurnal 2 n) |
| Caz optim în timp | O (1) |
| Caz mediu în timp | O (log 2 n) |
| Cel mai rău caz spațial | O (1) |
| Optim | da |
În informatică , căutarea dihotomică (sau căutare binară ) este un algoritm de căutare care identifică indicele unei valori date prezent într-un set ordonat de date. Căutarea dicotomă necesită acces aleatoriu la datele în care trebuie căutată.
Costul cercetării
Algoritmul caută un element dintr-un tablou care trebuie neapărat să fie sortat în ordine crescătoare, făcând în medie mai puține comparații decât o căutare secvențială și, prin urmare, mai rapid decât acesta, deoarece, prin exploatarea sortării, reduce la jumătate intervalul de căutare la fiecare pas.
Căutarea binară nu folosește niciodată mai mult decât (jurnalul de bază 2 al N rotunjit în sus) comparații pentru o lovitură de căutare sau o căutare ratată. Cu toate acestea, cu excepția cazului în care valorile celor doi indici extremi sunt verificați la fiecare iterație, căutarea binară durează întotdeauna același timp pe aceeași matrice pentru a căuta elemente chiar și în poziții diferite; căutarea secvențială trece în schimb de la O (n) ca cel mai rău caz la O (n / 2) în cazul mediu, până la O (1) dacă elementul se află în prima poziție. (cfr. O-grande )
Analiza algoritmului
Algoritmul este similar cu metoda utilizată pentru a putea primi ambele părți, adică pentru a găsi un cuvânt în dicționar: știind că vocabularul este sortat alfabetic, ideea este de a începe căutarea nu din primul element, ci din unul central, adică în mijlocul dicționarului. Comparați acest element cu cel pe care îl căutați:
- dacă se potrivește, căutarea se încheie indicând faptul că elementul a fost găsit;
- dacă este mai mare, căutarea se repetă pe elementele anterioare (adică pe prima jumătate a dicționarului), ignorând următoarele;
- dacă, pe de altă parte, este mai mică, căutarea se repetă pe următoarele elemente (adică pe a doua jumătate a dicționarului), aruncându-le pe cele anterioare.
Dacă ajunge la punctul în care toate articolele sunt aruncate, căutarea se încheie indicând faptul că valoarea nu a fost găsită. O curiozitate: algoritmul este aplicat și pentru a crea un program care ghicește un număr natural (aleatoriu sau ales de utilizator) inclus într-un interval. De fapt, această situație poate fi urmărită înapoi la căutarea unui element pe un set ordonat care are, ca date, toate numerele naturale incluse în interval.
Pseudo cod
Iată două versiuni ale algoritmului: versiunea iterativă și versiunea recursivă.
A indică vectorul în care se caută, p și r indică, respectiv, extremele inferioare și superioare, q indicele mediu ( rotunjit mai jos ) și v indică valoarea de căutat (în acest exemplu un număr întreg).
Ambele funcții returnează indexul în care se găsește valoarea (dacă este găsită) sau -1 pentru a indica faptul că nu a fost găsită.
Algoritm iterativ
Unde A este o matrice de numere întregi, p indică poziția primului element al matricei, r indică poziția ultimului element al matricei și v este elementul pe care îl caut.
funcție binarySearchIterative ( matrice A , int p , int r , int v )
dacă v <A [p] sau v> A [r]
return - 1 - înseamnă că v nu este prezent în A
în timp ce p <= r
q = ( p + r ) / 2
dacă A [ q ] == v
întoarcere q
dacă A [ q ] > v
r = q - 1
altceva
p = q + 1
întoarcere - 1
Algoritm recursiv
function binarySearch Recursive ( matrice A , int p , int r , int v )
dacă p > r
întoarcere - 1
dacă v <A [p] sau v> A [r]
întoarcere - 1
q = ( p + r ) / 2
dacă A [ q ] == v
întoarcere q
altfel dacă A [ q ] > v
return binarySearch Recursive ( A , p , q - 1 , v )
altceva
return binarySearch Recursive ( A , q + 1 , r , v )
Implementări
Urmează o implementare a aceluiași algoritm, tot în limbaj C. Aici recursivitatea nu este utilizată, astfel încât funcția este mai eficientă.
// list []: lista valorilor întregi de căutat
// n: valoarea întreagă a contorului de elemente din listă
// x: valoare întreagă de căutat
intNonRecursive binary search ( int list [], int n , int x )
{
int p , u , m ;
p = 0 ;
u = n - 1 ;
if ( x < list [ p ] || x > list [ u ] ) returnează -1 ;
while ( p <= u ) {
m = ( p + u ) / 2 ;
if ( lista [ m ] == x )
retur m ; // x valoare găsită la poziția m
if ( lista [ m ] < x )
p = m + 1 ;
altceva
u = m - 1 ;
}
// dacă programul atinge acest punct înseamnă că
// valoarea x nu este prezentă în listă, dar dacă a existat
// ar trebui să fie în poziția p (rețineți că p> u aici)
retur -1 ;
}
Parametrii funcției: lista este matricea de numere întregi pe care dorim să căutăm, n este numărul de elemente din matrice și x este valoarea de căutat. În timpul execuției, variabilele p și u , care inițial indică elementele extreme ale matricei, se apropie progresiv, îngustând din ce în ce mai mult zona în care se presupune că este dorită valoarea x dorită.
Iată o implementare recursivă în Java :
public class BinarySearch {
public int binarySearch ( int [] a , int p , int r , int k ) {
int q , s = - 1 ;
dacă ( p <= r ) {
q = ( p + r ) / 2 ;
if ( k < a [ q ] )
s = binarySearch ( a , p , q - 1 , k );
altfel dacă ( k > a [ q ] )
s = binarySearch ( a , q + 1 , r , k );
altfel dacă ( k == a [ q ] )
retur q ;
}
retur s ;
}
}
unde metoda binarySearch a clasei BinarySearch acceptă în mod evident ca intrare o matrice, doi indici cardinali și elementul de căutat.
Mai jos este o implementare a algoritmului foarte asemănătoare cu cele anterioare, dar într-un alt limbaj, C #.
Iată o implementare fără recursivitate.
/ * Funcție pentru căutare binară fără recursivitate
int [] matrice: lista valorilor întregi de căutat
element: întreg pentru a căuta * /
int Binary_Search ( int [] matrice , element int )
{
int start = 0 , end = array . Lungime - 1 , centru = 0 ;
while ( start <= end )
{
centru = ( început + sfârșit ) / 2 ;
if ( element < matrice [ centru ])
{
sfârșit = centru - 1 ;
}
altceva
{
if ( element > matrice [ centru ])
start = centru + 1 ;
altceva
centru de retur ; // Caz: element == matrice [centru]
}
}
retur - 1 ;
}
Cu recursiunea limbajului C # :
/ * Funcție pentru căutare binară cu recursivitate
int [] arr: matrice de valori întregi de căutat
n: valoare întreagă de căutat
start, end: valori întregi (bazate pe zero) ale indexului căutării de început și sfârșit în matrice
* /
int RecBinarySearch ( int [] arr , int n , int start , int end )
{
// Verificați consistența valorilor de intrare
// Poate fi abandonat pentru a optimiza execuția dacă controlul
// se face înainte de apelul funcției
if ( start > end || start < 0 || end < 0 )
retur - 1 ;
int middle = ( start + end ) / 2 ;
if ( n < arr [ mijloc ])
returnează RecBinarySearch ( arr , n , start , middle - 1 );
if ( n > arr [ mijloc ])
returnează RecBinarySearch ( arr , n , mijloc + 1 , sfârșit );
altceva
întoarcere la mijloc ;
}
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre cercetări dihotomice
