inte ens ett enda dagskort, när vi inte behöver söka efter något i vårt dagliga liv, bilnycklar, böcker, penna, mobilladdare och vad inte. Samma är livet för en dator, Det finns så mycket data som lagras i det, att när en användare ber om vissa data, datorn måste söka det minne för att leta efter data och göra den tillgänglig för användaren. Och datorn har sina egna tekniker för att söka igenom det minne snabbt, som du kan lära dig mer om i vår operativsystemhandledning.
vad händer om du måste skriva ett program för att söka ett visst nummer i en array? Hur ska du göra det?
Tja, för att söka ett element i en given array finns det två populära algoritmer tillgängliga:
- linjär sökning
- binär sökning
linjär sökning
linjär sökning är en mycket grundläggande och enkel sökalgoritm. I linjär sökning söker vi ett element eller värde i en given array genom att korsa arrayen från början tills önskat element eller värde hittas.
det jämför elementet som ska sökas med alla element som finns i matrisen och när elementet matchas framgångsrikt returnerar det indexet för elementet i matrisen, annars returnerar det -1.
linjär sökning tillämpas på osorterade eller oordnade listor, när det finns färre element i en lista.
funktioner i linjär sökalgoritm
- den används för osorterad och oordnad liten lista över element.
- den har en tidskomplexitet av O (n), vilket betyder att tiden är linjärt beroende av antalet element, vilket inte är dåligt, men inte så bra också.
- det har en mycket enkel implementering.
vi kommer att implementera den linjära sökalgoritmen i nästa handledning.
binär sökning
binär sökning används med sorterad array eller lista. I binär sökning följer vi följande steg:
- vi börjar med att jämföra elementet som ska sökas med elementet mitt i listan/arrayen.
- om vi får en matchning returnerar vi indexet för mittelementet.
- om vi inte får en matchning kontrollerar vi om elementet som ska sökas är mindre eller större än i värde än mittelementet.
- om elementet/numret som ska sökas är större i värde än mittnumret, väljer vi elementen på höger sida av mittelementet(eftersom listan / arrayen sorteras, alltså till höger kommer vi att ha alla siffror större än mittnumret) och börja om från steg 1.
- om elementet / numret som ska sökas är mindre i värde än mittnumret, väljer vi elementen på vänster sida av mittelementet och börjar igen från steg 1.
binär sökning är användbar när det finns ett stort antal element i en array och de sorteras.
så ett nödvändigt villkor för att binär sökning ska fungera är att listan/arrayen ska sorteras.
funktioner i binär sökning
- det är bra att söka igenom stora sorterade matriser.
- den har en tidskomplexitet av O (log n) vilket är en mycket bra tidskomplexitet. Vi kommer att diskutera detta i detaljer i binary Search tutorial.
- det har en enkel implementering.