# At søge

Måder at søge på:
* *Sekventiel* (også kaldet *lineær*)
* *Binær*

**Sekventiel søgning**
* **Løser**: At finde en bestemt ting i en usorteret samling.
* **Fordel**: Kan finde ting i en usorteret samling
* **Ulempe**: Meget langsom i forhold til binær søgning

Sekventiel søgning er som regel mere tidskrævende end binær søgning, det kræver i værste tilfælde at man tjekker alle ting i en samling. Hvis man har en samling på 10 milliarder ting så kan man risikere at skulle tjekke 10 milliarder ting.

Algoritme:

public static int sequentialSearch(int[] arr, int item) {
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] == item) {
			return i; // Returner indekset hvis item er fundet
		}
	}

	return -1; // Returner -1 hvis item ikke kan findes
}

**Binær søgning**
* **Løser**: At finde en bestemt ting i en sorteret samling.
* **Fordel**: Hurtig
* **Ulempe**: Samling skal være sorteret

Binær søgning er som regel meget hurtigere end sekventiel søgning, men det kræver at en samling er sorteret først. Herefter skal binær søgning kun tjekke ca. 34 ting for at finde en ting i **sorteret** samling bestående af 10 milliarder

Algoritme:

// Definerer en metode til binær søgning
private static int binSearch(int[] arr, int item) {
	int start = 0;
	int end = numbers.length - 1;

	while (start <= end) {
		int middle = start + ((end - start) / 2);
		
		if (arr[middle] == item) {
			return middle; // Returnerer indekset, hvis tallet er fundet
		}
		
		if (arr[middle] < item) {
			start = middle + 1; // Justerer søgeintervallet til højre halvdel
		}
		
		if (arr[middle] > item) {
			end = middle - 1; // Justerer søgeintervallet til venstre halvdel
		}
	}

	return -1; 	// Returnerer -1 hvis tallet ikke er fundet
}

Men, brug den indbyggede algoritme for binær søgning fra java.util.Arrays:

Arrays.binarySearch(numbers, tal-du-gerne-vil-finde);
// F.eks.:
Arrays.binarySearch(numbers, 22);

# Opsætning af problem

**Opsætte et array**
Definere et array som klasse variabel:

// Deklarerer og initialiserer et klassevariabel 'numbers' som et array med 10 elementer
private static int[] numbers = new int[10];

**Udskriv array**
Metode til at udskrive alle tal i vores array:

// Metode til at udskrive alle tal fra 'numbers' arrayet
private static void printNumbers() {
	// Loop gennem 'numbers' arrayet og udskriver hvert tal
	for (int i : numbers) {
		System.out.print(i + " - "); // Udskriver tallet og en separator
	}
	// Udskriver en ny linje, så det næste der bliver udskrivet
	// kommer på en ny linje
	System.out.println();
}

Dette giver:

0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 0 - 

**Sæt alle tallene i vores array til tilfælde tal**
Vi kan sætte alle tallene til et tilfældigt tal ved at bruge java.util.Random:
Først skal vi importere Random klassen:

import java.util.Random;

Herefter:

// Metode til at fylde 'numbers' arrayet med tilfældige tal
private static void randomizeNumbers() {
	// Initialiserer et Random objekt
	Random rand = new Random();
	// Loop gennem 'numbers' arrayet og tildel et tilfældigt tal til hvert element
	for (int i = 0; i < numbers.length; i++) {  
	    numbers[i] = rand.nextInt(100); // Genererer et tilfældigt tal mellem 0 og 99
	}
}

Efter 5 gange fås f.eks. disse tal:

94 - 60 - 85 - 53 - 97 - 80 - 30 - 91 - 85 - 52 -
65 - 17 - 46 - 49 - 43 - 87 - 40 - 38 - 84 - 80 -
72 - 20 - 49 - 11 - 54 - 52 - 34 - 97 - 45 - 33 -
69 - 95 - 66 - 39 - 82 - 91 - 33 - 19 - 62 - 81 -
81 - 61 - 24 - 9 - 7 - 54 - 41 - 57 - 70 - 17 -

Når vi initialiser et nyt Random object så kan vi give det et seed som gør at de samme tal genereres igen og igen. F.eks. kan vi give det seed 1337:

private static void randomizeNumbers() {
	// Initialiserer et Random objekt med et specificeret seed (1337)
	Random rand = new Random(1337);  
	for (int i = 0; i < numbers.length; i++) {  
	    numbers[i] = rand.nextInt(100); 
	}
}

Nu fås disse tal:

21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -

Vi har nu (med kommentarer):

// Importerer Random klassen fra java.util pakken
import java.util.Random;  
  
public class Main {
	// Deklarerer og initialiserer et klassevariabel 'numbers' som et array med 10 elementer
    private static int[] numbers = new int[10];  
  
    public static void main(String[] args) {
	    // Kalder metoden randomizeNumbers for at fylde 'numbers' arrayet med tilfældige tal
        randomizeNumbers();
        // Kalder metoden printNumbers for at udskrive tal fra 'numbers' arrayet
        printNumbers();  
    }  

	// Metode til at fylde 'numbers' arrayet med tilfældige tal
    private static void randomizeNumbers() {
	    // Initialiserer et Random objekt med et specificeret seed (1337)
        Random rand = new Random(1337);  
        // Loop gennem 'numbers' arrayet og tildel et tilfældigt tal til hvert element
        for (int i = 0; i < numbers.length; i++) {  
            numbers[i] = rand.nextInt(100); // Genererer et tilfældigt tal mellem 0 og 99
        }  
    }  
    
	// Metode til at udskrive alle tal fra 'numbers' arrayet
	private static void printNumbers() {
		// Loop gennem 'numbers' arrayet og udskriver hvert tal
		for (int i : numbers) {
			System.out.print(i + " - "); // Udskriver tallet og en separator
		}
		// Udskriver en ny linje, så det næste der bliver udskrivet
		// kommer på en ny linje
		System.out.println();
	}
}

Uden kommentare:

import java.util.Random;  
  
public class Main {
    private static int[] numbers = new int[10];  
  
    public static void main(String[] args) {
        randomizeNumbers();
        printNumbers();  
    }  

    private static void randomizeNumbers() {
        Random rand = new Random(1337);  
        for (int i = 0; i < numbers.length; i++) {  
            numbers[i] = rand.nextInt(100);
        }  
    }  
    
	private static void printNumbers() {
		for (int i : numbers) {
			System.out.print(i + " - ");
		}
		System.out.println();
	}
}

**Tips & tricks**
Vi kan skrive det her på en lidt kortere måde.

I stedet for at fylde vores 'numbers' array med tilfælde tal på den måde som vi gør her, så kan vi også 'bare' gøre følgende:

Random rand = new Random(1337); 
numbers = rand.ints(10, 0, 100).toArray();

Her bruger vi .ints() metoden fra java.util.Random og konvertere det til et array ved at bruge .toArray() metoden.

random.ints() har 3 parametre:
* **streamSize** (her 10) er antallet af integers der bliver genereret
* **randomNumberOrigin** (her 0) er den laveste værdi (inklusiv) som der kan genereres
* **randomNumberBound** (her 100) er den øvre grænse (ekslusiv) for de tal der kan genereres; dvs. her kan vi maks generere et tal der er 99.

Dette giver det samme som randomizeNumbers() metoden.

I stedet for at bruge printNumbers kan vi bruge .toString() metoden fra java.util.Arrays, først skal vi importere java.util.Arrays:

import java.util.Arrays;

Derefter bruge Arrays.toString på vores 'numbers' array.

Arrays.toString(numbers);

Hvis vi gerne vil udskrive det så skal vi give det til System.out.println:

System.out.println(Arrays.toString(numbers));

Med samme seed som før (1337) får vi nu:

[21, 44, 59, 22, 9, 48, 3, 4, 27, 67]
[21, 44, 59, 22, 9, 48, 3, 4, 27, 67]
[21, 44, 59, 22, 9, 48, 3, 4, 27, 67]
[21, 44, 59, 22, 9, 48, 3, 4, 27, 67]
[21, 44, 59, 22, 9, 48, 3, 4, 27, 67]

I stedet for:

21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -
21 - 44 - 59 - 22 - 9 - 48 - 3 - 4 - 27 - 67 -

Nu kan vi omskrive vores klasse som (uden kommentare):

import java.util.Arrays;
import java.util.Random;  
  
public class Main {
    private static int[] numbers = new int[10];  
  
    public static void main(String[] args) {
		Random rand = new Random(1337);
		numbers = rand.ints(10, 0, 100).toArray();
        System.out.println(Arrays.toString(numbers));
    }  
}

Med kommentare:

// Importerer nødvendige klasser
import java.util.Arrays;
import java.util.Random;  
  
public class Main {
	// Definerer et klassevariabel 'numbers'
    private static int[] numbers;  
  
    public static void main(String[] args) {
	    // Initialiserer Random objekt med et seed
		Random rand = new Random(1337);
		// Genererer et array af tilfældige tal og tildeler det til 'numbers'
		numbers = rand.ints(10, 0, 100).toArray();
		
		// Udskriver arrayet
        System.out.println(Arrays.toString(numbers));
    }  
}

# Sekventiel søgning
Sekventiel søgning fungerer på den måde at vi looper gennem hele arrayet for at se om vores ønskede tal kan findes, f.eks.:

// Definerer det tal, der skal søges efter
int item = 22;
// Loop gennem 'numbers' arrayet for at finde det specificerede tal
for (int i = 0; i < numbers.length; i++) {
	// Tjekker om det aktuelle element i 'numbers' arrayet er lig med det ønskede tal
	if (numbers[i] == item) {
		// Udskriver en besked til konsollen, hvis det ønskede tal er fundet, samt dets index
		System.out.println("We found " + item + " at index: " + i);  
	}  
}  

Her udskrives alle tallene i 'numbers' arrayet som er lig item.

Hvis vi gerne vil finde indekset på det første tal i vores 'numbers' array så kan vi gøre følgende:

// Definerer en metode til sekventiel søgning
private static int sequentialSearch(int item) {
	// Gennemgår hvert element i 'numbers' arrayet
	for (int i = 0; i < numbers.length; i++) {
		// Tjekker om det aktuelle element er det ønskede tal
		if (numbers[i] == item) {
			// Returnerer indekset, hvis tallet er fundet
			return i;
		}
	}

	// Returnerer -1, hvis tallet ikke er fundet
	return -1;
}

Hele programmet til videre med kommentare:

// Importerer nødvendige klasser
import java.util.Arrays;
import java.util.Random;  
  
public class Main {
	// Definerer et klassevariabel 'numbers'
    private static int[] numbers;  
  
    public static void main(String[] args) {
	    // Initialiserer Random objekt med et seed
		Random rand = new Random(1337);
		// Genererer et array af tilfældige tal og tildeler det til 'numbers'
		numbers = rand.ints(10, 0, 100).toArray();
		
		// Udskriver arrayet
        System.out.println(Arrays.toString(numbers));

		// Definerer det tal, der skal søges efter
		int item = 22;

		/** Sekventiel søgning **/
		System.out.println("Sequential search found " + item + " at index: " + sequentialSearch(item));
    } 
    
	// Definerer en metode til sekventiel søgning
	private static int sequentialSearch(int item) {
		// Gennemgår hvert element i 'numbers' arrayet
		for (int i = 0; i < numbers.length; i++) {
			// Tjekker om det aktuelle element er det ønskede tal
			if (numbers[i] == item) {
				// Returnerer indekset, hvis tallet er fundet
				return i;
			}
		}
	
		// Returnerer -1, hvis tallet ikke er fundet
		return -1;
	}
}

Uden kommentare:

import java.util.Arrays;
import java.util.Random;  
  
public class Main {
    private static int[] numbers = new int[10];  
  
    public static void main(String[] args) {
		Random rand = new Random(1337);
		numbers = rand.ints(10, 0, 100).toArray();
        System.out.println(Arrays.toString(numbers));

		int item = 22;
		System.out.println("Sequential search found " + item + " at index: " + sequentialSearch(item));
    } 

	private static int sequentialSearch(int item) {
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] == item) {
				return i;
			}
		}
		return -1;
	}
}

# Binær søgning
## Forklaring
Hvis vi har en samling som er sorteret kan vi bruge binær søgning.
Binær søgning fungerer på den måde at om den vi værdi vi ønsker at finde er større eller mindre end den værdi som findes i midten af vores samling.

F.eks. hvis vi har en samling af tal:

Array: [1, 4, 8, 12, 20, 37, 48, 57, 68, 78, 90, 100]
Index:  0, 1, 2,  3,  4,  5,  6,  7,  8,  9, 10,  11

Hvis vi så gerne vil prøve at finde tallet 20 så starter vi først ved at tjekke i midten.
Vi finder indekset til værdien i midten ved at bruge formlen:
$$(index_{start} + index_{end}) / 2$$

Hvor vi har vores indeks i starten som er 0, og vores indeks i slutningen som er 11. Det giver:
$$(0 + 11) / 2 = 5.5$$

Det er dog sådan at i Java og mange andre sprog så når man bruger division på integers så runder man nedad, dvs., det giver faktisk 5.

Så 37 er den værdi vi tjekker, som er større end 20, hvilket betyder at hvis 20 er i vores array så må det være i venstre side da vores array er sorteret fra mindst til størst. Så nu tjekker vi venstre side af vores array som er:

Array: [1, 4, 8, 12, 20]
Index:  0, 1, 2,  3,  4

Vi tjekker igen midten og finder tallet 8, som er mindre end 20. Det betyder så at vi skal tjekke højre side som er:

Array: [12, 20]
Index:   0,  1

Her er værdien i midten så 12. Så nu skal vi tjekke højre side:

Array: [20]
Index:   0

Hvilket jo så er 20.

## Sortere vores 'numbers' array
Først skal vi sortere vores 'numbers' array, det kan vi gøre med java.util.Arrays:

Arrays.sort(numbers);

## Algoritme
Binær søgning algorithme:

private static int binSearch(int item) {
	// Initialiserer start- og slutindeks
	int start = 0;
	int end = numbers.length - 1;

	// Fortsætter søgningen, så længe der er elementer tilbage i søgeintervallet
	while (start <= end) {
		// Beregner indekset for midterelementet og undgår overflow
		int middle = start + ((end - start) / 2);
		
		// Tjekker om midterelementet er det søgte tal
		if (numbers[middle] == item) {
			return middle; // Returnerer indekset, hvis tallet er fundet
		}
		
		// Tjekker om midterelementet er mindre end det søgte tal
		if (numbers[middle] < item) {
			start = middle + 1; // Justerer søgeintervallet til højre halvdel
		}

		// Tjekker om midterelementet er større end det søgte tal
		if (numbers[middle] > item) {
			end = middle - 1; // Justerer søgeintervallet til venstre halvdel
		}
	}

	// Returnerer -1, hvis tallet ikke er fundet
	return -1;
}

**Note**: Hvorfor bruger vi start + ((end - start) / 2) og ikke (start + end) / 2 for at finde middle?
For at undgå integer overflow. En integer har en størrelse på 32-bit dvs., at den mindste værdi kan være: $−2 147 483 648$ og den største værdi er: $2 147 483 647$

Lad os sige at man har følgende:

int x = 2_147_483_647;

Og man så øger den værdi med 1:

x++;

Hvad sker der så?
Overflow! Fordi tallet kan ikke gå op til 2 147 483 648 da det er større, det betyder så at værdien bliver −2 147 483 648.

Det betyder at hvis i vores tilfælde med binær søgning at vi har et stort array hvor start og end henholdsvis er:

int start = 1_000_000_000;
int end   = 2_000_000_000;

Hvis vi så har:

int middle = (start + end) / 2;
// (1_000_000_000 + 2_000_000_000) / 2
// Dette giver: 3_000_000_000 / 2
// Men dette er jo større end 2_147_483_648, så i Java får vi:
// -1_294_967_296 / 2 = -647_483_648
// Som jo er helt ubrugeligt som et indeks

Men hvis vi har den anden formel:

int middle = start + ((end - start) / 2);
// 1_000_000_000 + ((2_000_000_000 - 1_000_000_000) / 2)
// Dette giver: 1_000_000_000 + (1_000_000_000 / 2)
//            = 1_000_000_000 + 500_000_000
//            = 1_500_000_000
// Som er det vi gerne vil have

I den første metode giver 'start + end' et tal der er større end 'end' hvilket kan resultere i overflow hvis summen af de to er ekstremt store. I den anden metode kan man ikke få en værdi som er større end 'end'.

**Tip**: Der en indbygget binarySearch algoritme i java.util.Arrays:

Arrays.binarySearch(numbers, 22);

Her søger vi efter tallet '22' i vores 'numbers' array.

## Hele programmet
Med kommentare:

// Importerer nødvendige klasser
import java.util.Arrays;
import java.util.Random;  
  
public class Main {
	// Definerer et klassevariabel 'numbers'
    private static int[] numbers;  
  
    public static void main(String[] args) {
	    // Initialiserer Random objekt med et seed
		Random rand = new Random(1337);
		// Genererer et array af tilfældige tal og tildeler det til 'numbers'
		numbers = rand.ints(10, 0, 100).toArray();

		// Sorter arrayet
		Arrays.sort(numbers);

		// Udskriver arrayet
        System.out.println(Arrays.toString(numbers));

		// Definerer det tal, der skal søges efter
		int item = 22;

		/** Sekventiel søgning **/  
		System.out.println("Sequential search found " + item + " at index: " + sequentialSearch(item));  
		  
		/** Binær søgning **/  
		System.out.println("Binary search found " + item + " at index: " + binSearch(item));
    }

	// Definerer en metode til sekventiel søgning
	private static int sequentialSearch(int item) {
		// Gennemgår hvert element i 'numbers' arrayet
		for (int i = 0; i < numbers.length; i++) {
			// Tjekker om det aktuelle element er det ønskede tal
			if (numbers[i] == item) {
				// Returnerer indekset, hvis tallet er fundet
				return i;
			}
		}
	
		// Returnerer -1, hvis tallet ikke er fundet
		return -1;
	}

	// Definerer en metode til binær søgning
	private static int binSearch(int item) {
		// Initialiserer start- og slutindeks
		int start = 0;
		int end = numbers.length - 1;
	
		// Fortsætter søgningen, så længe der er elementer tilbage i søgeintervallet
		while (start <= end) {
			// Beregner indekset for midterelementet og undgår overflow
			int middle = start + ((end - start) / 2);
			
			// Tjekker om midterelementet er det søgte tal
			if (numbers[middle] == item) {
				return middle; // Returnerer indekset, hvis tallet er fundet
			}
			
			// Tjekker om midterelementet er mindre end det søgte tal
			if (numbers[middle] < item) {
				start = middle + 1; // Justerer søgeintervallet til højre halvdel
			}
	
			// Tjekker om midterelementet er større end det søgte tal
			if (numbers[middle] > item) {
				end = middle - 1; // Justerer søgeintervallet til venstre halvdel
			}
		}
	
		// Returnerer -1, hvis tallet ikke er fundet
		return -1;
	}
}

Uden kommentare:

import java.util.Arrays;
import java.util.Random;  
  
public class Main {
    private static int[] numbers;  
  
    public static void main(String[] args) {
		Random rand = new Random(1337);
		numbers = rand.ints(10, 0, 100).toArray();

		Arrays.sort(numbers);

        System.out.println(Arrays.toString(numbers));

		int item = 22;

		System.out.println("Sequential search found " + item + " at index: " + sequentialSearch(item));  
		  
		System.out.println("Binary search found " + item + " at index: " + binSearch(item));
    }

	private static int sequentialSearch(int item) {
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] == item) {
				return i;
			}
		}
		
		return -1;
	}

	private static int binSearch(int item) {
		int start = 0;
		int end = numbers.length - 1;
	
		while (start <= end) {
			int middle = start + ((end - start) / 2);

			if (numbers[middle] == item) {
				return middle;
			}
			
			if (numbers[middle] < item) {
				start = middle + 1;
			}
	
			if (numbers[middle] > item) {
				end = middle - 1;
			}
		}
	
		return -1;
	}
}