Lineair zoeken en binair zoeken

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Zoekalgoritmen

Zoeken is een kernoperatie
- Meerdere manieren
Algoritmen die een element in een collectie zoeken:
- Lineair zoeken
- Binaire zoekopdracht

Lineair zoeken

Door elk element loopen

Een schematische weergave van een lijst met ongesorteerde getallen.

Element gevonden
- algoritme stopt
- retourneert het resultaat
Element niet gevonden
- algoritme gaat door

Lineair zoeken

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

Lineair zoeken - complexiteit

Complexiteit: $O(n)$

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen.

15 ???

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Er is een variabele genaamd first die naar de eerste positie van de lijst wijst.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Er is een variabele genaamd first die naar de eerste positie van de lijst wijst en een andere variabele genaamd last die naar de laatste positie wijst.

15 ???

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


  while first <= last:

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Er is een variabele genaamd first die naar de eerste positie van de lijst wijst, een andere variabele genaamd last die naar de laatste positie wijst, en een andere variabele genaamd middle die naar de middelste positie wijst.

15 ???

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

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

15 ???
Vergelijk search_value met het item in het midden van de lijst

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]:

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Er is een variabele genaamd first die naar de eerste positie van de lijst wijst, een andere variabele genaamd last die naar de middelste positie min één wijst, en een andere variabele genaamd middle die naar de middelste positie wijst. De elementen tussen de eerste en middelste posities zijn groen gekleurd.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

15 ???
Vergelijk search_value met het item in het midden van de lijst

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:

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Er is een variabele genaamd first die naar de middelste positie plus één wijst, een andere variabele genaamd last die naar de laatste positie wijst, en een andere variabele genaamd middle die naar de middelste positie wijst. De elementen tussen de eerste en middelste posities zijn groen gekleurd.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. De middle-pointer is verplaatst en wijst naar het element tussen first en last. De elementen tussen de eerste en middelste posities zijn groen gekleurd.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. De last-pointer is verplaatst en wijst naar hetzelfde getal als de first-pointer.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. De middle-pointer is verplaatst en wijst naar hetzelfde getal als de first- en last-pointers.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. De first-, last- en middle-pointers wijzen naar hetzelfde getal, 15, dat vergeleken wordt met het getal 15.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht

Alleen voor gesorteerde lijsten

Schematische weergave van een lijst met gesorteerde getallen. Het getal 15 is omcirkeld.

15 ???
Vergelijk search_value met het item in het midden van de lijst

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

Binaire zoekopdracht - complexiteit

Complexiteit: $O(\log{}n)$

Grafische weergave van lineair zoeken en binaire zoeken.

Laten we oefenen!

Datastructuren en algoritmen in Python