2.1.3

Searching algorithm

Searching a list

Linear

• Starting from the beginning of a data set each item is checked in turn to see if it is the one being searched for until the item is found or the end of the data set is reached

• A searching algorithm that searches each item in a list from start to end sequentially and compares each value to the one wanted until the item is found or the end of the data set is reached

While loop

items=["wolf","bunny","pig","ferret","squirrel","chicken","puppy","fox"]

search=input()

found=False

index=0

while found==False and index<len(items):

if items[index]==search:

found=True

else:

index+=1

if found==True:

print("Found")

else:

print("not found")

For loop

items=["wolf","bunny","pig","ferret","squirrel","chicken","puppy","fox"]

search=input()

found=False

for index in range (len(items)):

if items[index]==search:

found=True

if found==True:

print("found")

else:

print("not found")

Binary search

• It only works in a sorted list

• The middle item of the list is checked first

• If the item searched for it less than the item the right side of the list is discarded and a binary search is carried out on the left side of the list

• Mid point is Low+High DIV 2

  • If value is lower, High then becomes MID-1

  • If value is higher, Low then becomes MID+1

names=["Ali","Ben","Carl","Joe","Ken","Lara","Mo","Oli","Pam","Stan","Tara"]

Low=0

High=len(names)-1

Mid=0

search=input()

Found=False

while Found==False and Low<=High:

Mid=(Low+High)//2

if names[Mid]==search:

Found=True

print("Item found")

elif names[Mid]>search:

High=Mid-1

else:

Low=Mid+1

if Found==False:

print("Item not found")