In diesem Tutorial lernen Sie die lineare Suche kennen. Außerdem finden Sie Arbeitsbeispiele für die lineare Suche in C, C ++, Java und Python.
Die lineare Suche ist der einfachste Suchalgorithmus, der nach einem Element in einer Liste in sequentieller Reihenfolge sucht. Wir beginnen an einem Ende und überprüfen jedes Element, bis das gewünschte Element nicht gefunden wird.
Wie funktioniert die lineare Suche?
Die folgenden Schritte werden ausgeführt, um k = 1in der folgenden Liste nach einem Element zu suchen .
Array, nach dem gesucht werden soll
- Beginnen Sie mit dem ersten Element und vergleichen Sie k mit jedem Element x.
Vergleiche mit jedem Element - Wenn
x == k, geben Sie den Index zurück.
Element gefunden - Sonst Rückgabe nicht gefunden.
Linearer Suchalgorithmus
LinearSearch (Array, Schlüssel) für jedes Element im Array, wenn item == value seinen Index zurückgibt
Beispiele für Python, Java und C / C ++
Python Java C C ++ # Linear Search in Python def linearSearch(array, n, x): # Going through array sequencially for i in range(0, n): if (array(i) == x): return i return -1 array = (2, 4, 0, 1, 9) x = 1 n = len(array) result = linearSearch(array, n, x) if(result == -1): print("Element not found") else: print("Element found at index: ", result)
// Linear Search in Java class LinearSearch ( public static int linearSearch(int array(), int x) ( int n = array.length; // Going through array sequencially for (int i = 0; i < n; i++) ( if (array(i) == x) return i; ) return -1; ) public static void main(String args()) ( int array() = ( 2, 4, 0, 1, 9 ); int x = 1; int result = linearSearch(array, x); if (result == -1) System.out.print("Element not found"); else System.out.print("Element found at index: " + result); ) )
// Linear Search in C #include int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result); )
// Linear Search in C++ #include using namespace std; int search(int array(), int n, int x) ( // Going through array sequencially for (int i = 0; i < n; i++) if (array(i) == x) return i; return -1; ) int main() ( int array() = (2, 4, 0, 1, 9); int x = 1; int n = sizeof(array) / sizeof(array(0)); int result = search(array, n, x); (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result; )
Komplexe lineare Suche
Zeitkomplexität: O (n)
Raumkomplexität: O(1)
Lineare Suchanwendungen
- Für Suchvorgänge in kleineren Arrays (<100 Elemente).
