ikke engang en enkelt dagpas, når vi ikke behøver at søge efter noget i vores daglige liv, bilnøgler, bøger, pen, mobil oplader og hvad ikke. Det samme er en computers liv, der er så meget data gemt i den, at når en bruger beder om nogle data, skal computeren søge i hukommelsen for at lede efter dataene og gøre dem tilgængelige for brugeren. Og computeren har sine egne teknikker til at søge gennem det hukommelse hurtigt, som du kan lære mere om i Vores operativsystem tutorial serie.
hvad hvis du skal skrive et program for at søge et givet nummer i et array? Hvordan vil du gøre det?
nå, for at søge et element i et givet array er der to populære algoritmer tilgængelige:
- lineær søgning
- binær søgning
lineær søgning
lineær søgning er en meget grundlæggende og enkel søgealgoritme. I lineær søgning søger vi et element eller en værdi i et givet array ved at krydse arrayet fra starten, indtil det ønskede element eller den ønskede værdi findes.
det sammenligner det element, der skal søges, med alle de elementer, der findes i arrayet, og når elementet matches med succes, returnerer det indekset for elementet i arrayet, ellers vender det tilbage -1.
lineær søgning anvendes på usorterede eller uordnede lister, når der er færre elementer på en liste.
funktioner af lineær søgealgoritme
- det bruges til usorteret og uordnet lille liste over elementer.
- det har en tidskompleksitet på O(n), hvilket betyder, at tiden er lineært afhængig af antallet af elementer, hvilket ikke er dårligt, men ikke så godt også.
- det har en meget enkel implementering.
vi implementerer den lineære søgealgoritme i den næste tutorial.
binær søgning
binær søgning bruges med sorteret array eller liste. I binær søgning følger vi følgende trin:
- vi starter med at sammenligne det element, der skal søges med elementet midt på listen/arrayet.
- hvis vi får en kamp, returnerer vi indekset for mellemelementet.
- hvis vi ikke får et match, kontrollerer vi, om det element, der skal søges, er mindre eller større end i værdi end det midterste element.
- hvis det element/nummer, der skal søges, er større i værdi end det midterste tal, vælger vi elementerne på højre side af det midterste element(da listen / arrayet er sorteret, derfor til højre, vil vi have alle numrene større end det midterste tal), og start igen fra trin 1.
- hvis det element / nummer, der skal søges, er mindre i værdi end det midterste tal, vælger vi elementerne på venstre side af det midterste element og starter igen fra trin 1.
binær søgning er nyttig, når der er et stort antal elementer i et array, og de sorteres.
så en nødvendig betingelse for, at Binær søgning fungerer, er, at listen/arrayet skal sorteres.
funktioner af binær søgning
- det er dejligt at søge gennem store sorterede arrays.
- det har en tidskompleksitet af O(log n), hvilket er en meget god tidskompleksitet. Vi vil diskutere dette i detaljer i den binære søgning tutorial.
- det har en simpel implementering.