Lineare Suche

1. Linearer Suchalgorithmus
2. Beispiel für lineare Suche
3. Implementierung des linearen Suchalgorithmus
4. Komplexität des linearen Suchalgorithmus

Die lineare Suche ist der einfachste Suchalgorithmus. Er wird auch sequentielle Suche genannt, weil wir bei diesem Algorithmus nach einem Element suchen, indem wir das gesamte Array durchlaufen und jedes Element mit dem gewünschten Element vergleichen, um eine Übereinstimmung zu finden. Wenn das gewünschte Element gefunden wird, wird der Index dieses Elements zurückgegeben; andernfalls wird die Suche fortgesetzt, bis das Array erschöpft ist. Wir können auch nach mehreren Vorkommen eines Elements innerhalb eines Arrays suchen. Es wird meist verwendet, um Elemente innerhalb eines unsortierten Arrays zu suchen. Sie wird in der Praxis nicht verwendet, da sie viel langsamer ist als die binäre Suche.

Linearer Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein Element - X - finden.

Beispiel für lineare Suche

Angenommen, wir haben das Array: (5, 3, 4, 2, 1, 6).

• Fall 1: Wir wollen nach X = 5 suchen.

Das erste Element selbst ist eine Übereinstimmung, und wir geben den Index 0 zurück. (Bester Fall)

• Fall 2: Wir wollen nach X = 1 suchen.

Wir durchlaufen das Array und erreichen den Index 4, um eine Übereinstimmung zu finden und geben diesen Index zurück. (Mittlerer Fall)

• Fall 3: Wir wollen nach X = 9 suchen.

Wir durchlaufen das Array, finden aber keine Übereinstimmung, wenn wir das letzte Element des Arrays erreichen. Wir geben -1 zurück. (Schlechtester Fall)

Implementierung des linearen Suchalgorithmus

Linearer Suchalgorithmus für eine einzelne Übereinstimmung

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) return i;
  }
  return -1;
}

int main() {
  int n = 5;
  int arr[] = {2, 4, 0, 1, 9};
  int x = 1;
  int result = search(arr, n, x);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index: " << result;
}

Linearer Suchalgorithmus für mehrere Übereinstimmungen

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
  vector<int> ans;
  // Traverse the array sequentially
  for (int i = 0; i < n; i++) {
    if (arr[i] == x) {
      ans.push_back(i);
    }
  }
  return ans;
}

int main() {
  int n = 9;
  int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
  int x = 1;
  vector<int> res = search(arr, n, x);
  if (res.empty()) {
    cout << "Element not found!!";
  } else {
    cout << "Element found at ";
    for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
    }
  }
}

Komplexität des linearen Suchalgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Die Zeitkomplexität des linearen Suchalgorithmus ist O(n).

• Bester Fall

Die Zeitkomplexität im besten Fall ist O(1). Sie tritt auf, wenn das zu suchende Element das erste Element ist, das im Array vorhanden ist.

• Schlechtester Fall

Der ungünstigste Fall tritt ein, wenn das gesuchte Element nicht im Array vorhanden ist oder sich am letzten Index des Arrays befindet. Die Zeitkomplexität im ungünstigsten Fall ist O(n).

Raumkomplexität

Die Raumkomplexität dieses Algorithmus hängt von der Anzahl der Übereinstimmungen und der verwendeten Implementierung ab. Im Allgemeinen wird die Platzkomplexität mit O(1) angegeben, kann aber höher sein, wenn mehrere übereinstimmende Indizes in einem Array gespeichert sind.