Gebrauch
Der lineare Suchalgorithmus ist einer der einfachsten Suchalgorithmen, um den Index eines ELements in einem Array zu finden.
Der Array kann unsortiert sein.
Spezifikationen
Der lineare Suchalgorithmus hat eine best-case Performance von O(1), worst-case von O(n) und eine durchschnittliche Performance von O(n).
Da der Algorithmus keinen weiteren Array benötigt, ist seine Space-Complexity immer O(1).
Funktionsweise
Bei dem linearen Suchalgorithmus wird über den Array iteriert und den momentanen Index zurückgegeben, falls das Element bei diesem Index dem gesuchten Wert entspricht.
Da der Algorithmus abgebrochen wird, falls das Element gefunden wurde, kann man sicher sein, dass das Element nicht in dem Array vorhanden ist, falls nach dem Iterieren noch nichts zurückgegeben wurde.
Beispielcode
Dies ist ein in Python geschriebener Beispielcode:
# arr ist der Array, in dem der Wert val gesucht wird
def linearSearch(arr, val):
# Man iteriert über den ganzen Array
for i in range(len(arr)):
# Der untersuchte Wert stimmt mit dem Gesuchten überein
if arr[i] == val:
# Der gerade analysierte Index wird zurückgegeben
return i
# Der Wert ist nicht in dem Array vorhanden
return -1
Dies ist ein in Java geschriebener Beispielcode:
Es können selbstverständlich auch andere Datentypen gebraucht werden.
// arr ist der Array, in dem der Wert val gesucht wird
public static int linearSearch(int[] arr, int val) {
// Man iteriert über den ganzen Array
for (int i = 0; i < arr.length; i++) {
// Der untersuchte Wert stimmt mit dem Gesuchten überein
if (arr[i] == val) {
// Der gerade analysierte Index wird zurückgegeben
return i;
}
}
// Der Wert ist nicht in dem Array vorhanden
return -1;
}
Animiertes Beispiel
Ändere die Position des Sliders, um den gesuchten Wert zu bestimmen und die Animation zu starten.
Legende
- Zu findender Wert
- Untersuchter Wert
- Noch nicht untersuchter Wert
- Ausgeschlossener Wert