Algoritme: Lineær Søgning

Implementer algoritmen Lineær Søgning. Gennemgå elementerne i listen fra start til slut, indtil søgeværdien er fundet. Du kan bruge Pseudokoden som reference til algoritmen. Når din algoritme er færdig, kan du afprøve den under Test Cases.

Pseudokode

FUNKTION lineær_søgning(liste, værdi): FOR HVER indeks i fra 0 til længde af liste: HVIS element ved indeks i == værdi: Returner indeks i Returner -1

Test Cases

Løsning

Lineær søgning gennemløber listen fra indeks 0 til n-1. For hvert element sammenlignes værdien med søgeværdien.

                Indsæt solution code
              

Tidskompleksitet

  • Bedste tilfælde: O(1)
  • Værste tilfælde: O(n)

Hvorfor virker den?

Algoritmen garanterer korrekthed fordi alle elementer inspiceres sekventielt indtil værdien findes.