Lineare Suche erklärt

Was ist lineare Suche?

Angenommen, Sie erhalten eine Liste oder ein Array von Elementen. Sie suchen nach einem bestimmten Artikel. Wie machst du das?

Suchen Sie die Nummer 13 in der angegebenen Liste.

Lineare Suche 1

Sie sehen sich nur die Liste an und da ist es!

Lineare Suche 2

Wie können Sie einem Computer sagen, dass er ihn finden soll?

Ein Computer kann zu einem bestimmten Zeitpunkt nicht mehr als den Wert anzeigen. Es nimmt also ein Element aus dem Array und prüft, ob es mit dem übereinstimmt, was Sie suchen.

Lineare Suche 3

Der erste Artikel stimmte nicht überein. Fahren Sie also mit dem nächsten fort.

Lineare Suche 4

Und so weiter…

Dies erfolgt so lange, bis eine Übereinstimmung gefunden wurde oder bis alle Elemente überprüft wurden.

Lineare Suche 5

In diesem Algorithmus können Sie anhalten, wenn das Element gefunden wurde, und müssen dann nicht weiter suchen.

Wie lange würde die lineare Suchoperation dauern? Im besten Fall könnten Sie Glück haben und der Gegenstand, den Sie sich ansehen, befindet sich möglicherweise an der ersten Position im Array!

Im schlimmsten Fall müssten Sie sich jedoch jedes einzelne Element ansehen, bevor Sie das Element an der letzten Stelle finden oder bevor Sie feststellen, dass sich das Element nicht im Array befindet.

Die Komplexität der linearen Suche ist daher O (n).

Wenn das zu durchsuchende Element im ersten Speicherblock leben würde, wäre die Komplexität: O (1).

Der Code für eine lineare Suchfunktion in JavaScript wird unten gezeigt. Diese Funktion gibt die Position des gesuchten Elements im Array zurück. Wenn das Element nicht im Array vorhanden ist, gibt die Funktion null zurück.

Beispiel in Javascript

function linearSearch(arr, item) { // Go through all the elements of arr to look for item. for (var i = 0; i < arr.length; i++) { if (arr[i] === item) { // Found it! return i; } } // Item not found in the array. return null; }

Beispiel in Ruby

def linear_search(target, array) counter = 0 while counter < array.length if array[counter] == target return counter else counter += 1 end end return nil end

Beispiel in C ++

int linear_search(int arr[],int n,int num) { for(int i=0;i

Example in Python

def linear_search(array, num): for i in range(len(array)): if (array[i]==num): return i return -1

Global Linear Search

What if you are searching the multiple occurrences of an element? For example you want to see how many 5’s are in an array.

Target = 5

Array = [ 1, 2, 3, 4, 5, 6, 5, 7, 8, 9, 5]

This array has 3 occurrences of 5s and we want to return the indexes (where they are in the array) of all of them.

This is called global linear search and you will need to adjust your code to return an array of the index points at which it finds your target element.

When you find an index element that matches your target, the index point (counter) will be added in the results array. If it doesn’t match, the code will continue to move on to the next element in the array by adding 1 to the counter.

def global_linear_search(target, array) counter = 0 results = [] while counter < array.length if array[counter] == target results << counter counter += 1 else counter += 1 end end if results.empty? return nil else return results end end

Why linear search is not efficient

There is no doubt that linear search is simple. But because it compares each element one by one, it is time consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So you should also learn about bubble sort, quick sort and other more efficient algorithms.

Other search algorithms:

  • How to implement quick sort
  • Binary search algorithm
  • Jump search algorithm
  • Search algorithms explained with examples
  • Implement a binary search algorithm in Java without recursion
  • More info on search algorithms

Original text