Binær søketidskompleksitet

Binært søk er et splitt-og-erobre-paradigme. Den søker etter et element i en sortert matrise. I denne artikkelen blir det bare vurdert å stigende. Elementet å søke etter kalles målverdien. Målverdien kan kanskje ikke finnes i matrisen.

Søket begynner med å sammenligne målverdien med den midterste elementet i den sorterte matrisen. Hvis antallet varer i matrisen er jevn, regnes varen ved halvparten av tallet som det midterste elementet. Hvis målverdien er den samme som mellomvaren, er målverdiindeksen blitt funnet. Hvis de ikke er de samme, er målverdien enten større eller mindre enn mellomvaren. Hvis den er større, vil den nedre halvdelen av matrisen bli forlatt for søket for å fortsette i øvre halvdel. Hvis den er mindre, vil den øvre halvdelen av matrisen bli forlatt, for at søket skal fortsette i den nedre halvdelen.

Søket fortsetter ved å dele halvparten valgt i to igjen. En sammenligning mellom målverdien og den midterste varen til denne nye halvdelen er gjort. Hvis de ikke er de samme, er denne halvparten delt igjen i to, og av samme grunner ble den forrige halvdelen delt. Hvis målverdien ikke er den samme som den nye midterste varen, fortsetter divisjonen.

Når målverdien og en medianverdi (element) er den samme, er det å erobre. Der og da stopper søket. Hvis målverdien ikke er i matrisen, vil søket stoppe ved en endelig midtre vare, som ikke er lik målverdien.

Denne artikkelen tar sikte på å gi en takknemlighet som kalles tidskompleksitet for hastigheten på binær søk.

Artikkelinnhold

• INNLEDNING - Se ovenfor
• Binær søkeillustrasjon
• Tidskompleksitet og binær søk
• Koding i c
• Konklusjon

Binær søkeillustrasjon

Tenk på den sorterte listen:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Der heltallet, 3, må søkes. Selvfølgelig vil søk fra begynnelsen ta tre operasjoner. Å bruke binær søk vil imidlertid ta fire hovedoperasjoner som følger:

Målverdien er 3. Å dele listen i to gjør 8 midtre vare.

Er 8 det samme som 3?

Nei. Siden 3 er mindre enn 8, vil søket fokusere på den nedre halvdelen. Det er en hovedoperasjon utført.

Deling i to igjen gjør 4 til den nye midtre varen.

Er 4 det samme som 3?

Nei. Siden 3 er mindre enn 4, vil søket fokusere på den nye nedre halvdelen. Det er den andre hovedoperasjonen som er utført.

Deling i to igjen gjør to til den nye midtre varen.

Er 2 det samme som 3?

Nei. Siden 3 er større enn 2, vil søket da fokusere på den nye øvre halvdelen. Det er den tredje hovedoperasjonen utført.

Deling i to igjen gjør 3 den nye midtre varen, av en halv (underliste) lengde, en. Den nye og siste midterste varen er nå 3.

Er 3 det samme som 3?

Ja. Målverdien er funnet. Det er den fjerde og siste hovedoperasjonen utført.

Når det er 16 varer, kan maksimalt 4 hovedoperasjoner gjøres. Hvis det var 16 elementer, og målverdien var i området og ikke ble funnet, ville 4 hovedoperasjoner fortsatt ha funnet sted. For eksempel i følgende liste: for eksempel:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

Det er fortsatt 16 varer. En målverdi på 3 ville ha endt til verdien av 5, med fortsatt 4 hovedoperasjoner.

Tidskompleksitet og binær søk

Worst-case ytelse

Worst-case ytelse refererer til saken der målverdien er funnet ved den siste hovedoperasjonen, eller målverdien er i verdiene og ikke er funnet ved den siste hovedoperasjonen.

Når antallet varer er 16, vil maksimalt antall operasjoner alltid være 4.

16 = 2⁴
4 = Logg₂(16)

La n være 16. Så,

4 = Logg₂(n)

Hvis n er 8, vil maksimalt antall operasjoner være 3 = log₂(8). Hvis n er 32, vil maksimalt antall operasjoner være 5 = log₂(32).

Det verste tilfellet kompleksitet (relativ hastighet) for binær søk sies å være:

O (log₂(n))

Der den store O og dens parenteser har logg₂(n) er notasjonen for tidskompleksitet. Det er ganske enkelt skrevet som:

O (log n)

Best case ytelse

Anta at målverdien var 8 for den første listen ovenfor. I dette tilfellet ville den første hovedoperasjonen ha funnet plasseringen av målverdien. Dette er best case-ytelsen. Tidskompleksiteten for denne best case-forestillingen er skrevet som:

O (1)

Hvor 1 betyr en hovedoperasjon.

Koding i c

En C -kode binær søkefunksjon er:

#inkludere
int binarysearch (int arr [], int Target, int n)
int loindex = 0;
int upindex = n - 1;
// Forsikre deg om at vi fremdeles har elementer i listen å søke i
mens (loindex mål)
UpIndex = MiddleNx;
annet
loindex = Middlex + 1;


// returner et negativt tall når vi ikke finner målet i matrisen
return -1;

LOINDEX betyr den laveste indeksen på halvparten (underliste). UPINDEX betyr den øverste indeksen på halvparten (underliste). I begynnelsen er Loindex 0 og upindex er 15 når n er 16. Mens-loop-tilstanden sikrer at inndelingen fortsetter til Loindex er den samme som Upindex hvis målverdien ikke er funnet ennå.

En passende C hovedfunksjon for denne koden er:

int main (int argc, char ** argv)

int n = 16;
int -mål = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
int indexFound = binarysearch (arr, mål, n);
printf ("%d \ n", indeksfound);
retur 0;

Konklusjon

Denne artikkelen diskuterte den binære søketidskompleksiteten og la vekt på følgende:

Den verste tidskompleksiteten for binær søk er:
O (log n)

Best-case tidskompleksitet for binær søk er:
O (1)