Typer av sökalgoritmer

Sökalgoritmer utgör en viktig del av många program. Vissa sökningar innebär att du letar efter en post i en databas, som att leta upp din post i IRS-databasen. Andra sökalgoritmer trålar genom ett virtuellt utrymme, som de som letar efter de bästa schackdragen. Även om programmerare kan välja mellan många söktyper väljer de den algoritm som bäst matchar databasens storlek och struktur för att ge en användarvänlig upplevelse.

Den linjära sökningen är den valda algoritmen för korta listor, eftersom den är enkel och kräver minimal kod att implementera. Den linjära sökalgoritmen tittar på det första listobjektet för att se om du söker efter det och i så fall är du klar. Om inte, tittar den på nästa punkt och vidare genom varje post i listan.

Binär sökning är en populär algoritm för stora databaser med poster sorterade efter numerisk nyckel. Exempelkandidater inkluderar IRS-databasen knappad med personnummer och DMV-posterna knappade med körkortsnummer. Algoritmen börjar i mitten av databasen -- om ditt målnummer är större än mittentalet fortsätter sökningen med den övre halvan av databasen. Om ditt målnummer är mindre än mittnumret fortsätter sökningen med den nedre halvan av databasen. Den fortsätter att upprepa denna process och halverar databasen varje gång tills den hittar posten. Denna sökning är mer komplicerad än den linjära sökningen, men för stora databaser är den mycket snabbare än en linjär sökning.

En trädsökning fungerar bara om data passar in i en trädstruktur. Databasen börjar med en rot som går till ett fåtal objekt, som var och en går till några fler objekt och så vidare tills du har ett träd. Ett exempel är schackspelet. Den nuvarande styrelsepositionen är roten. De lagliga dragen från denna position representerar ett steg ner i trädet, och så vidare tills spelaren hittar den styrelseposition som lämnar honom i den bästa positionen.

En genetisk algoritmsökning är en av teknikerna bakom artificiell intelligens. Den söker efter en "optimal lösning" uttryckt som en datasträng — till exempel listan över inre dimensioner för en jetmotor som ger maximal dragkraft. Sökningen börjar med en slumpmässig population av strängar och testar var och en, behåller de bästa och föder upp dem för att få nästa generation. Programmet fortsätter att upprepa denna process tills det kommer fram till en optimal lösningssträng.