Linear & Binary search

Question 1

Wat is het basisidee achter een binaire zoekopdracht?

Answer 1

Een binaire zoekopdracht verdeelt de zoekruimte telkens in tweeën om sneller bij het doel te komen. Dit werkt alleen op gesorteerde arrays.

Question 2

Wat is de belangrijkste voorwaarde om een binaire zoekopdracht te gebruiken?

Answer 2

De array moet gesorteerd zijn om een binaire zoekopdracht te kunnen gebruiken.

Question 2

Welk zoekalgoritme is efficiënter voor grote, ongeordende datasets: lineair zoeken of binair zoeken?

Answer 2

Lineair zoeken is efficiënter voor ongeordende datasets omdat binair zoeken alleen werkt op gesorteerde arrays.

Question 3

Wat zijn de overeenkomsten tussen lineair en binair zoeken?

Answer 3

Beide algoritmen zijn bedoeld om een specifiek element in een array te vinden.
Beide retourneren de index van het element als het wordt gevonden, of -1 als het niet wordt gevonden.

Question 4

Wat zijn de verschillen tussen lineair en binair zoeken?

Answer 4

Tijdcomplexiteit: Lineair zoeken heeft een tijdcomplexiteit van O(N), terwijl binair zoeken O(log N) is.
Dataset: Lineair zoeken werkt op zowel gesorteerde als ongesorteerde arrays, terwijl binair zoeken alleen op gesorteerde arrays werkt.
Methode: Lineair zoeken controleert elk element één voor één, terwijl binair zoeken de array telkens in tweeën splitst.

Question 5

Schrijf een codefragment in Java voor een lineaire zoekopdracht in een array.

Answer 5

public int linearSearch(int[] arr, int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
return i; // Key gevonden, retourneer index
}
}
return -1; // Key niet gevonden
}

Question 6

Schrijf een codefragment in Java voor een binaire zoekopdracht in een gesorteerde array.

Answer 6

public int binarySearch(int[] arr, int key) {
int lowerBound = 0;
int upperBound = arr.length - 1;

while (lowerBound <= upperBound) {
    int mid = (lowerBound + upperBound) / 2;
    if (arr[mid] == key) {
        return mid; // Key gevonden, retourneer index
    } else if (arr[mid] < key) {
        lowerBound = mid + 1; // Zoeken in de bovenste helft
    } else {
        upperBound = mid - 1; // Zoeken in de onderste helft
    }
}
return -1; // Key niet gevonden }