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$ $\log _{2}1/\varepsilon$ $1+\log _{2}N$

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 .