2.1 Linear search

Question 1

linear search

Answer 1

sequential

starts at the beginning of the list and moves though item by item until it finds the matching item or reaches the end of the list

Question 2

brute force

Answer 2

a linear search is a brute force algorithm

it does not contain any specialist techniques, only raw computing power

it is not an efficient method as each search starts at the beginning and keeps going until the item is found or the list ends

Question 3

efficiency of a linear search

Answer 3

if there are 500 items:

best case: the search item is the first one found

worst case: the search item is the last item found

average case: 500 + 1/2 = 250.5/251

Question 4

Describe in words an algorithm for carrying out a linear search [6]

Answer 4

1) if the length of the list is zero, stop
2) start at the beginning of the list
3) compare the list item with the search criterion
4) if the are the same, then stop
5) if they are not the same, then move to the next item
6) repeat steps 3 to 5 until the end of the list is reached

Question 5

Design an algorithm expressed in pseudocode to ask a user for a search item and carry out a linear search on data stored in an array to find that item [6]

Answer 5

(there is no length method for an array in OCR pseudocode)

item = input("Please enter the search item")
found = False
index = 0

while found = False AND index <= array
length - 1
     if array[index] == item then
         found = True
         print("Item found.")
     else
         index = index + 1
     endif
endwhile

if found == False then
print(“Item not found.”)
endif