Linear search

Linear search is an algorithm also known as sequential search . It's the simplest search algorithm ever.

The task is to find an element in a list or an array with n elements. You go through the list element by element until you find it. The search effort increases linearly with the number of elements in the list.

The more efficient binary search can only be used for ordered lists.

For unordered lists there is a randomized algorithm called Lazy Select , which with a relatively high probability can find the nth element of a list with respect to an order faster than in linear time.

complexity

The linear search is in the complexity class O (n) , since in the worst case (when the searched value cannot be found) it requires n comparisons.

If the data is randomly distributed, then (n + 1) / 2 comparison operations are required on average .

In the best case, the first element of the list is what you are looking for.

When the number of elements in a list is small, it is often the most efficient method.

Implementations (examples)

Implementation in pseudocode

BEGINN LinearSearch

  EINGABE: (S)uchschlüssel, (A)rray

  VARIABLE: N = Anzahl Elemente im Array 'A'
  VARIABLE: SucheErfolgreich = falsch
  VARIABLE: i = 0

  FÜR i BIS N ODER SucheErfolgreich
    WENN A[i] = S
    DANN SucheErfolgreich = wahr

  WENN SucheErfolgreich = wahr
  DANN AUSGABE: i
  SONST AUSGABE: Suche nicht erfolgreich

ENDE

Example implementation in Ruby

# Falls der Wert nicht gefunden wird, gibt die Methode nil zurück.
def lineare_suche(liste, gesucht)
  liste.each_with_index do |wert, index|
    return index if wert == gesucht
  end

  nil
end

# bzw.
liste.index(gesucht)

Example implementation in Delphi or Free Pascal

// Durchsucht ein Array of Integer nach einem gesuchten Integer-Wert.
// Wird der gesuchte Wert gefunden, gibt die Funktion den Index des Wertes zurück.
// Falls der Wert nicht gefunden wird, gibt die Funktion -1 zurück.
function LineareSuche(gesucht : integer; ADaten : array of integer) : integer;
var
  c : integer;
begin
  Result := -1;

  for c := Low(ADaten) to High(ADaten) do
    if gesucht = ADaten[c] then
      Result := c;
end;

Example implementation in Objective CAML

 let rec linsuche = function
     ([],a) -> false
     | (x::t,a) -> if x = a then true else linsuche(t,a);;

Example implementation in Java

The example returns the value -1if the element searched for does not exist in the array daten. Otherwise the position of the element is returned.

public static int lineareSuche(final int gesucht, final int[] daten) {
    for (int i = 0; i < daten.length; i++) {
        if (daten[i] == gesucht) {
            return i;
        }
    }
    return -1;
}

Example implementation in Python

Finds all search keys in the list.

def lineare_suche(liste, gesucht):
    idxs = []
    for index, element in enumerate(liste):
        if element == gesucht:
            idxs.append(index)
    return idxs
# bzw.
lineare_suche = lambda l,g : [i for i,e in enumerate(l) if g == e]

Finds the first occurrence of the search key in a list.

def lineare_suche(liste, gesucht):
    for index, element in enumerate(liste):
        if element == gesucht:
            return index
# bzw. gibt es schon
lineare_suche = lambda l,g : l.index(g) if g in l else None

Example implementation in C

Finds the first search key (integer) in the list.

#include <stdio.h>
/*
int*daten = Zeiger auf zu durchsuchende Daten
int datenlaenge = Größe des zu durchsuchenden "Arrays"
int suche = Gesuchte Ganzzahl
*/
int suche_sequenziell(int*daten, int datenlaenge, int suche) {
	int i;
	for (i=0;i<datenlaenge;i++)
		if (daten[i]==suche)
			return i;
	return -1;
}

/* Beispielaufruf */
int main(void) {
	int datenArray[10] = { 81, 1203, 180, 42, 10, 566, 102, 751, 54, 648 };
	int pos = suche_sequenziell(datenArray, 10, 42);
/* -1 für nicht gefunden, ansonsten (erste) Position im Array, mit 0 beginnend */
	if (pos<0)
		printf("Nicht gefunden");
	else
		printf("Gefunden an Position %d",pos);
	return 0;
}

See also

• List of algorithms