Searching algorithms

Linear search

Look through each item in the list, is it the one you want, if not move to the next.

best case big o

O(1), because the first item you look at will be the one you want

Code

def linearSearch(namelist,nameSought):
    index = -1
    i = 0
    found = False
    while i < len(namelist) AND NOT found:
          if namelist[i] == nameSought:
            index = i
            found = True
        i = i + 1       
    return index

Big O

index = -1
i = 0
found = False

+3

while i < len(namelist) AND NOT found:
        ...
        index = i
        found = True
      ...

2n

therefore Big O = 2n+3 which simplifies to O(n)

Example question

Describe the steps that a linear search would take to find Anna in student name

studentnames = ["Rob", "Anna", "Huw", "Emma", "Patrice", "Iqbal"] 

Examine Rob. Rob does not equal to Anna, so move on. Examine Anna. Anna is equal to Anna so item found.

Binary search

Looking at the middle item, then ignoring half of the list that depending on if the middle point is less then or bigger then the middle point.

Best case Big O

O(1), because the first item you look at will be the one you want

Code

function binarySearch(aList, itemSought)
  found = False
  index = -1
  first = 0
  last = len(aList)-1
  while first <= last and found == False:
    midpoint = (first + last) div 2
    if aList[midpoint] == itemSought:
      found = True
      index = midpoint
    else:
      if aList[midpoint] < itemSought:
        first = midpoint + 1
      else:
        last = midpoint – 1
  return index

Big O

〖𝑙𝑜𝑔〗_2 (𝑛)=𝑦 ↔2^𝑦=𝑛