Summary GCSE OCR Computer Science revision notes for Algorithms

Data set – group of data items

Two search algorithms: linear and binary

What you are looking for – search criteria

Linear search = start with he first item in the set and compare it to the search
criteria

If no match is found, then the next one is compared, continuing until a match is
found or the end of the set is reached – sequential search algorithm

Data_set = [“cat”, “dog”, “lion”, “penguin”, “ant”]


data_set_length = 5

search_criteria = "penguin"

match = false



FOR (i = 0 TO (data_set_length - 1))

IF data_set[i] == search_criteria THEN

match = true

exit loop

END IF

NEXT i



IF (match == true) THEN

PRINT "Match found"

ELSE

PRINT "No match found"

END IF

 Performs well with small and medium-sized lists

 Fairly simple to code

 The data set does not need to be in any particular order
(some algorithms need an ordered list)

,  It doesn't break if new items are inserted into the list.

Disadvantages
 May be too slow to process large lists or data sets

 If the search criteria only matches the last item in the list,
the search has to go through the entire list to find it.

Binary search algorithm must be arranged in order.

Then split into two and two again

Hover over each line to see the comment about it.



data_set = [2, 4, 5, 6, 9, 21, 50, 77, 91]

data_set_length = 9

search_criteria = 50

LB = 0

UB = data_set_length - 1

match = false



WHILE match == false AND LB != UB

MidPoint = roundup((UB - LB)/2) + LB

IF data_set[MidPoint] == search_criteria THEN

match = true

ELSE IF data_set[MidPoint] < search_criteria THEN

LB = MidPoint + 1

ELSE

UB = MidPoint - 1

END IF

END WHILE



IF match == true THEN

PRINT 'Match found'

ELSE