Lineare Suche und Binärsuche

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software engineer

Suchalgorithmen

Suchen ist eine Grundoperation
- Mehrere Vorgehensweisen
Algorithmen zum Suchen eines Elements in einer Sammlung:
- Lineare Suche
- Binärsuche

Lineare Suche

Durch alle Elemente iterieren

Schematische Darstellung einer Liste unsortierter Zahlen.

Element gefunden
- Algorithmus stoppt
- gibt Ergebnis zurück
Element nicht gefunden
- Algorithmus läuft weiter

Lineare Suche

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Lineare Suche – Komplexität

Komplexität: $O(n)$

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen.

15 ???

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Es gibt eine Variable namens first, die auf die erste Position der Liste zeigt.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Es gibt eine Variable namens first, die auf die erste Position der Liste zeigt, und eine weitere namens last, die auf die letzte Position zeigt.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Es gibt eine Variable namens first, die auf die erste Position der Liste zeigt, eine weitere namens last, die auf die letzte Position zeigt, und eine weitere namens middle, die auf die mittlere Position zeigt.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

Binärsuche

Gilt nur für sortierte Listen

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Es gibt eine Variable namens first, die auf die erste Position zeigt, eine weitere namens last, die auf die Position Mitte minus eins zeigt, und eine weitere namens middle, die auf die mittlere Position zeigt. Die Elemente zwischen first und middle sind grün markiert.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

Binärsuche

Gilt nur für sortierte Listen

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Es gibt eine Variable namens first, die auf Position Mitte plus eins zeigt, eine weitere namens last, die auf die letzte Position zeigt, und eine weitere namens middle, die auf die mittlere Position zeigt. Die Elemente zwischen first und middle sind grün markiert.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Der middle-Zeiger wurde verschoben und zeigt auf das Element zwischen first und last. Die Elemente zwischen first und middle sind grün markiert.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Der last-Zeiger wurde verschoben und zeigt auf dieselbe Zahl wie der first-Zeiger.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Der middle-Zeiger wurde verschoben und zeigt auf dieselbe Zahl wie die Zeiger first und last.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Die Zeiger first, last und middle zeigen auf dieselbe Zahl, 15, die mit der Zahl 15 verglichen wird.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Binärsuche

Gilt nur für sortierte Listen

Schematische Darstellung einer Liste mit sortierten Zahlen. Die Zahl 15 ist eingekreist.

15 ???
Vergleiche search_value mit dem Element in der Mitte der Liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

Binärsuche – Komplexität

Komplexität: $O(\log{}n)$

Grafische Darstellung von linearer Suche und Binärsuche.

Lass uns üben!

Datenstrukturen und Algorithmen in Python