Inledning

Att hitta data snabbt är minst lika viktigt som att t.ex. kunna sortera data. Vi kommer här att presentera två algoritmer för att hitta data.

Sökalgoritmer är faktiskt betydligt lättare än sorteringsalgoritmer. Den främsta anledningen till att vi tar upp sökalgoritmer är att kursmålen i Programmering 1 tydligt tar upp just sökalgoritmer. Dessutom måste man kunna minst två för betyget A.

Som alla vet så är det lättare att hitta något när vi har ordning på saker och ting. Detsamma gäller data, därför utgår vi från att den data vi söker i redan är sorterad.

Sekventiell sökning

Vi börjar med ett fält med heltalen {3, 6, 10, 5, 2, 1, 8}.

Hur skall vi kunna hitta ett värde t.ex. värdet 2 i fältet?

Om du tänker något i stil med; "vi går igenom alla tal i fältet tills vi stöter på värde 2". Då är du på rätt spår för så fungerar sekventiell sökning. Vi kommer att hitta vårt värde (2) på index 4. Märk att för sekventiell sökning så behöver inte datan i fältet vara sorterad.

Skulle vi implementera detta i en metod så kan det se ut såhär:

public int SekventiellSök(int[] data, int värde)
{
	int index = -1;
	
	if(data == null)
		return index;

	for(int i=0; i<data.Length; i++)
	{
		if(data[i] == värde)
		{
			index = i;
			break;
		}
	}
	return index;
}

Som inparametrar har vi data samt värde. data innehåller alla heltal som vi söker i och värde är det tal vi söker efter. Som sas tidigare så behöver inte data vara sorterad för att vi ska finna ett svar.

Vi börjar med en liten extra koll så att inte data är null. Vi returnerar snabbt -1 i så fall.

Vi undersöker varje tal i fältet tills dess att vi hittar det vi söker. Då avbryter sparar vi undan det index vi är på (i) och avbryter loop'en med break. Sist i metoden så returnerar vi det index som talar om var i data som vi eventuellt har funnit det vi sökte.

Vad händer om vi söker efter ett tal som inte finns med? Ja då måste algoritmen gå igenom alla tal innan vi med säkerhet kan säga att vi inget hittade. Det värde som returneras då är -1. Eftersom -1 inte är ett giltigt index i ett fält så passar detta värde bra för att signalera att vi inte fann det vi sökte efter.

En annan implementation av samma algoritm:

public int SekventiellSök(int[] data, int värde)
{
	if(data == null)
		return -1;

	for(int i=0; i<data.Length; i++)
	{
		if(data[i] == värde)
			return i;
	}
	return -1;
}

Binär sökning

Om vi istället har data som är sorterad så kan vi använda oss av binär sökning. Tänk dig en telefonkatalog.

Skall vi söka efter "Sven Svensson" så vet vi att han finns i slutet av katalogen. En algoritm kan inte jobba så då den ej kan anta något i förväg. Istället måste en algoritm hantera alla fall. Hur gör vi?

Binär sökning gå till som så att vi slår upp den mittersta sidan i katalogen. Finns "Sven Svensson" här så är vil klara. Tyvärr så var det "Nilsson" som listades här. Det betyder då att "Sven Svensson" inte fanns med i den första havlan av katalogen så vi skall koncentrera oss på den sista havlan.

Den sista halvan delar vi åter igen på mitten och slår upp. Denna gång var det "Tranström" som listades. Det betyder att vi måste kika mellan mittuppslaget i katalogen och där vi befinner oss nu. Det området delar vi igen på mitten och slår upp.

Så håller vi på tills dess att vi hittar det vi söker efter. Vi delar hela tiden in kvarstående område i två delar och ser om vi 1) hittat rätt, 2) ska leta före eller, 3) ska leta efter områdets mitt.

Vi kikar på några bilder innan vi hoppar på implementationen. I exemplet så ska vi söka efter värdet 15 i datan {3, 5, 6, 7, 9, 10, 12, 15, 16, 17, 19, 21, 22, 23 } .

Turkos färg markerar start-index, grön färg markerar stop-index och rosa färg markerar mitt-index.

Steg 1. Vid start så sätts start till 0 och stop till max-index för fältet. Mitt-index beräknas genom att ta (start + stop) / 2. 13 delat med 2 blir vanligtvis 6,5 men eftersom vi använder oss av heltal och heltalsdivision så kommer vi automatiskt få en konvertering till heltal. 6,5 kommer alltså uttryckas som heltal vilket blir 6. Därför blir mittvärdet satt till index 6.

Steg 2. Eftersom vårt valda mitt-värde inte är det vi letar efter så fortsätter vi med att sätta start till mitt + 1 = index 7. Värdet vi letar efter måste ligga "framför" mitt-värdet i fältet. Nytt mitt-index blir (7 + 13) / 2 = index 10.

Steg 3. Eftersom mitt-värdet i steg 2 (19) inte är värdet vi söker efter så fortsätter vi. Denna gång ligger värdet vi söker "bakom" mitt-index. Därför justerar vi stop-index till mitt-index - 1 = index 9. Nytt mitt-index är (7 + 9) / 2 = index 8.

Steg 4. Fortfarande ingen sökträff. Mitt-värdet är nu 16. Nytt stop-index blir 7 och nytt mitt-index blir då (7 + 7) / 2 = 7. Alltså både start, stop och mitt-index är nu 7. Var finns på index 7? Jo värdet 15 som eftersöktes.

Dags för en implementation.

public int BinärSök(int[] data, int värde)
{
	if(data == null)
		return -1;
	
	int start = 0;
	int stop = data.Length - 1;

	while(start <= stop)
	{
		int mitt = (start + stop) / 2;
		if(data[mitt] < värde)
			start = mitt + 1;
		else if(data[mitt] > värde)
			stop = mitt - 1;
		else
			return mitt;
	}
	
	return -1;
}

Skulle vi söka efter ett tal som inte finns med i vår data så kommer antingen start eller stop-index slutligen att justeras så att start-index ligger efter stop-index. Skulle detta inträffa så har vi inte hittat det vi söker efter och kommer att avsluta med att reurnera -1.

Prestanda

Bästa fallet är detsamma för sekventiell sökning som för binär sökning. I båda fallen har vi tur att första talet vi undersöker är det som eftersöks. Det krävs då endast 1 jämförelse.

I värsta fallet så är talet vi söker efter det sista tal vi undersöker i sekventiell sökning. Vi har då jämfört N tal, där N är storleken på datan. Samma gäller om vi söker efter ett tal som inte finns i datan, då har vi också det värsta fallet. För binär sökning är värsta fallet betydligt bättre. Eftersom vi hela tiden delar området med två så är frågan hur många gånger kan vi dela datans storlek N på två? Matematisk kan vi skriva detta som log₂(N).

Medelfallet för sekventiell sökning är att vi hittar rätt tal när vi gått igenom hälften av alla tal, dvs N / 2. För binär sökning är det svårare att komma fram till men svaret är log₂(N) - 1. Steget innan maximalt antal steg som krävs. Vi kan ta en titt på en bild för att se vilka tal som endast kan hittas på maximalt antal steg, dvs. att vi inte har turen att upptäcka dem tidigt. Vi använder samma data som i exemplet innan och markerar värden som hittas tidigt med orange och övriga som gula.

Det är nu tydligare att se att ungefär hälften av alla tal hittas "sista steget". Hade vi haft mer data så hade det faktiskt varit något färre än hälften som hittas "sista steget". Man förväntas hitta svaret precis "steget innan" i medelfallet för binär sökning.

Vad är det då för skillnad på N och log₂(N) då? Ganska stor faktiskt när man tittar på större tal för N.