Linear Search

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.