Lineare Suche in Swift und Python

Nach einer kurzen Übersicht zur Big-O-Notation folgt die lineare Suche. Die lineare Suche ist der einfachste Suchalgorithmus. Sie ist auch unter der Bezeichnung sequentielle Suche bekannt. Ziel ist es, einen einzelnen Wert in einem Array zu finden. Dabei wird der gesuchte Wert mit den im Array vorhandenen Werten verglichen. Als Ergebnis erhält man im nachfolgenden Beispiel den Index (hier: 2) des gefundenen Wertes (hier: 17) oder die Information, dass der Wert nicht im Array enthalten ist. Wie man sich denken kann, hat diese Suche einen O(n)-Wert.

array linear search

Swift 3

Für ein Array mit Integer-Werten könnte der Code (in Swift 3.1) folgendermaßen aussehen:

let myArray = [4, 12, 17, 33, 11, 53]

func linearSearch(_ array: [Int], _ number: Int) -> String {
    for (i, value) in array.enumerated() where value == number {
    return String(i)
    }
return "Value is not in the array."
}

var r1 = linearSearch(myArray, 17)
// -> 2
var r2 = linearSearch(myArray, 10)
// -> Value is not in the array.

Python 3

Der Python3-Code für die lineare Suche ist ebenfalls leicht verständlich. Auch dieses Beispiel zeigt wie nach dem Index eines Integer-Wertes gesucht werden kann (in einer Liste).

my_list = [4, 12, 17, 33, 11, 53]

def linear_search(l, n):
    for i in range(0, len(l)):
        if l[i] == n:
            print(str(n) + " found at index " + str(i))

linear_search(my_list, 17)

Dieser Beitrag wird fortgesetzt im Artikel „Lineare Suche II„.