Søgning
Der er 2 typer af søgninger. En er linear Search og den anden er Binary Search. Linear er den simple og kan bruges på u-sorterede samlinger som Array, Lister osv. Linear er også den simpleste at implimentere, så den kikke vi på først.
| Linear Søgning | |
| Når vi søger på denne her måde starter vi ved første position og leder hele arrayet igennem til sidste position, og hvis vi på vejen finder det vi leder efter, kan vi stoppe søgningen og svar at vi har fundet det vi ledte efter (returnere true f.eks). |
 |
| Som du ser her på billedet til højre så flytter vi pilen til højre og tjekker om det vi leder efter er at finde i den aktuelle position i arrayet. På billedet her, kan vi se at vi akkurat er placeret der hvor 5 tallet er i arrayet og det er det vi søger efter. Hvis vi i stedet havde søgt efter f.eks 10 så ville vi køre igennem hele arrayet og ikke finde det vi søger. |
 |
| Kode | |
|
using System;
namespace Searching
{
class Program
{
static void Main(string[]
args)
{
int[] arr = { 6, 1, 7, 2, 5, 9, 3 };
Searching s = new
Searching();
bool b = s.find(arr, 3);
Console.WriteLine(b);
}
}
class Searching
{
public bool find(int[]
ar, int tal)
{
bool svar = false;
int i = 0;
while (i < ar.Length)
{
if (tal == ar[i])
{
svar = true;
}
i = i + 1;
}
return svar;
}
}
}
|
|
| Output | |
 |
|
| Binary Søgning | |
| Denne søgning kræver at arrayet er SORTERET. For at styr søgningen bruger vi 3 variabler, min, mid og max. Når vi starter, som billedet her viser, står min på start positionen og max på slut positionen, og mid står midt i mellem. Her søger vi på 3. Algoritmen sammenligner mid værdien med det som søges efter. Her er mid 8 og vi søger 3, og næste iteration ses på følgende billede. |
 |
| Her har vi flytte max til den position som mid stod på minus en, fordi vi har undersøgt position 8 så vi behøves ikke at tjekke den igen. Min står hvor den startede. Mid flyttes nu til en ny position som ligger i mellem min og max og vi er heldige her, fordi den har akkurat den værdi som vi søger nemlig 3. Hvis arrayet ikke indeholder det som vi søger, så vil min blive lig med eller større end max, og så ved vi at nu kan vi stoppe at søge. |
 |
| Kode | |
|
using System;
namespace BinarySearch
{
class Program
{
static void Main(string[]
args)
{
int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
Searching s = new
Searching();
bool b = s.binarySearch(arr, 4);
Console.WriteLine(b);
}
}
class Searching
{
public bool binarySearch(int[]
ar, int tal)
{
bool svar = false;
int min = 0;
int max = ar.Length - 1;
int mid = (((max - min) / 2) + min);
bool kør = true;
while (kør == true)
{
printUd(min, max, mid, ar, tal);
if (min >= max)
{
kør = false;
}
if (tal > ar[mid])
{
min = mid + 1;
}
if (tal < ar[mid])
{
max = mid - 1;
}
if (tal == ar[mid])
{
svar = true;
kør = false;
}
mid = (((max - min) / 2) + min);
}
return svar;
}
private void printUd(int min,
int max, int middle, int[] liste, int søgeTal)
{
string listen = "";
for (int i = 0; i < liste.Length; i++)
{
String indsæt = liste[i] + "";
if (i == max)
indsæt = indsæt + "]";
if (i == min)
indsæt = "[" + indsæt;
if (i == middle)
indsæt = "(" + indsæt + ")";
listen = listen + "-" + indsæt;
}
Console.WriteLine(listen);
}
}
} |
|
| Output | |
 |
|