Linjärsökning och binärsökning

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Sökalgoritmer

Sökning är en grundläggande operation
- Flera tillvägagångssätt
Algoritmer som söker efter ett element i en samling:
- Linjärsökning
- Binärsökning

Linjärsökning

Loopar igenom varje element

En schematisk bild av en lista med osorterade tal.

Element hittat
- algoritmen stannar
- returnerar resultatet
Element ej hittat
- algoritmen fortsätter

Linjärsökning

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

Linjärsökning – komplexitet

Komplexitet: $O(n)$

Binärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal.

15 ???

Binärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. En variabel kallad first pekar på listans första position.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Binärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. En variabel kallad first pekar på listans första position och en variabel kallad last pekar på den sista positionen.

15 ???

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


  while first <= last:

Binärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. En variabel kallad first pekar på listans första position, en variabel kallad last pekar på den sista positionen och en variabel kallad middle pekar på mittenpositionen.

15 ???

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

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

Binärsökning

Gäller endast sorterade listor

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. En variabel kallad first pekar på listans första position, en variabel kallad last pekar på mittenpositionen minus ett och en variabel kallad middle pekar på mittenpositionen. Elementen mellan first och middle är markerade i grönt.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. En variabel kallad first pekar på mittenpositionen plus ett, en variabel kallad last pekar på den sista positionen och en variabel kallad middle pekar på mittenpositionen. Elementen mellan first och middle är markerade i grönt.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Mittenpekaren har förflyttats och pekar på elementet mellan first och last. Elementen mellan first och middle är markerade i grönt.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Mittenpekaren har förflyttats och pekar på elementet mellan first och last. Elementen mellan first och middle är markerade i grönt. Elementet som middle pekar på, 17, ska jämföras med talet 15.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Last-pekaren har förflyttats och pekar på samma tal som first-pekaren.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Mittenpekaren har förflyttats och pekar på samma tal som first- och last-pekarna.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Pekarna first, last och middle pekar alla på samma tal, 15, som ska jämföras med talet 15.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning

Gäller endast sorterade listor

Schematisk bild av en lista med sorterade tal. Talet 15 är inringat.

15 ???
Jämför search_value med elementet i mitten av listan

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ärsökning – komplexitet

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

Grafisk jämförelse av linjärsökning och binärsökning.

Nu kör vi en övning!

Datastrukturer och algoritmer i Python