Binär sökning
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från
versionen som granskades den 20 mars 2021; kontroller kräver
29 redigeringar .
Binär (binär) sökning (även känd som bisektionsmetoden eller dikotomi ) är en klassisk algoritm för att hitta ett element i en sorterad array (vektor) som använder att dela arrayen i halvor. Används inom datavetenskap , beräkningsmatematik och matematisk programmering .
Ett specialfall av binär sökning är bisektionsmetoden , som används för att hitta rötterna till en given kontinuerlig funktion på ett givet intervall.
Hitta ett element i en sorterad array
- Bestämma värdet på ett element i mitten av en datastruktur. Det resulterande värdet jämförs med nyckeln.
- Om nyckeln är mindre än mittvärdet, utförs sökningen i den första hälften av elementen, annars - i den andra.
- Sökningen reduceras till det faktum att värdet på mittelementet i den valda halvan återigen bestäms och jämförs med nyckeln.
- Processen fortsätter tills antingen elementet med nyckelvärdet hittas eller tills sökintervallet är tomt.
Även om koden är ganska enkel, finns det några fallgropar.
- Koden (first + last) / 2är felaktig om firstoch lastindividuellt passar in i deras typ, men first+last inte [1] . Om arrayer av en så stor storlek är teoretiskt möjliga måste man ta till knep:
- Använd kod first + (last - first) / 2som definitivt inte kommer att leda till spill när du hanterar icke-negativa heltal och first<last.
- Om firstoch last är pekare eller iteratorer är sådan kod den enda korrekta, eftersom den inte bryter mot abstraktionen (operationen "pekare + pekare" är redan felaktig). Naturligtvis, för att bevara komplexiteten i algoritmen, behöver vi snabba operationer "pekare+nummer → pekare", "pekare-pekare → nummer".
- Om firstoch last är signerade typer, utför beräkningen i den osignerade typen: ((unsigned)first + (unsigned)last) / 2. I Java kommer följande kod att fungera: (first + last) >>> 1(signerad binär addition är samma som osignerad, Java garanterar detta beteende även vid spill, och hela denna formel fungerar på signerade nummer som osignerade).
- Skriv en beräkning i assembler med bärflaggan . Något som add eax, b; rcr eax, 1. Men det är inte tillrådligt att använda långa typerfirst + (last - first) / 2 , det är snabbare.
- Fel av ett är vanliga i binära sökningar , och varje sådant fel förvandlas till en loop , skip eller out-of-bounds-array. Därför är det viktigt att testa sådana fall: en tom array ( n=0), ett element ( n=1), letar efter ett saknat värde (för stort, för litet och någonstans i mitten), letar efter det första och sista elementet.
- Ibland krävs det att, om xdet finns flera instanser i kedjan, inte någon, utan nödvändigtvis den första (som ett alternativ: den sista; eller inte alls x, men elementet efter det) hittas. [2] Till exempel, en C++- funktion hittar den första av lika och hittar elementet efter x. Om de inte hittas returnerar båda platsen där de ska infogas.std::lower_boundstd::upper_bound
Forskaren Jon Bentley hävdar att 90 % av eleverna, när de utvecklar en binär sökning, glömmer att ta hänsyn till något av dessa krav. Och även i koden som Jon skrev själv och gick från bok till bok smög sig ett fel in: koden är inte resistent mot översvämningar [1] .
Java-implementeringsexempel
int binarySearch ( int [] arr , int nyckel ) {
int låg = 0 ;
int hög = arr . längd - 1 ;
while ( låg <= hög ) {
int mid = ( låg + hög ) >>> 1 ;
int midVal = arr [ mitt ] ;
if ( midVal < nyckel )
låg = mitten + 1 ;
annat om ( midVal > nyckel )
hög = mitten -1 ; _
annan
återvända mitten ; // nyckel hittades
}
return - ( låg + 1 ); //-nyckeln hittades inte.
}
Applikationer
De praktiska tillämpningarna av den binära sökmetoden varierar:
- Utbredd inom datavetenskap i relation till sökning i datastrukturer. Till exempel utförs sökning i datamatriser med nyckeln som är tilldelad vart och ett av elementen i matrisen (i det enklaste fallet är själva elementet nyckeln).
- Det används också som en numerisk metod för att hitta en ungefärlig lösning på ekvationer (se Bisektionsmetod ).
- Metoden används för att hitta extremumet för objektivfunktionen och är i detta fall en villkorad endimensionell optimeringsmetod . När en funktion har ett reellt argument är det möjligt att hitta en lösning upp till inom tiden . När argumentet är diskret, och initialt ligger på ett segment med längden N , kommer sökandet efter en lösning att ta tid. Slutligen, för att söka efter ett extremum, säg, för vissheten om minimum , kasseras i nästa steg en av ändarna av det betraktade segmentet, vars värde är maximalt.
![\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
![\log _{2}1/\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/721f641bab10f7d5d4ad19443f420459d3c9f78b)
![{\displaystyle 1+\log _{2}N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93810dfe31a1304cacfdf94c5a3e0f68c9ed4247)
Se även
Anteckningar
- ↑ 1 2 Extra, Extra - Läs allt om det: Nästan alla binära sökningar och sammanslagningar är brutna Arkiverad 2 december 2013 på Wayback Machine // Joshua Bloch, Google Research; översättning — Nästan alla implementeringar av binär sökning och merge sort har en bugg Arkiverad 24 november 2013 på Wayback Machine
- ↑ I C++ std::lower_bound hittar den första förekomsten av x, och hittar std::upper_bound elementet som följer x.
Litteratur
- Levitin A. V. Kapitel 4. Nedbrytningsmetod: Binär sökning // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 180-183. — 576 sid. — ISBN 978-5-8459-0987-9
- Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beräkningsmetoder för ingenjörer. — M .: Mir, 1998.
- Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriska metoder. - 8:e uppl. - M . : Laboratory of Basic Knowledge, 2000.
- Wirth N. Algoritmer + datastrukturer = Program . - M . : " Mir ", 1985. - S. 28 .
- Volkov E. A. Numeriska metoder. — M .: Fizmatlit, 2003.
- Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
- Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .
- Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.
- Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. - Energoatomizdat, 1972.
- Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa olinjära programmeringsproblem. — M .: MEPhI, 1982.
- Robert Sedgwick. Grundläggande algoritmer i C. Grundläggande/Datastrukturer/Sortering/Sökning. - St Petersburg. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .
Länkar