Year 11 refine Searching and sorting algorithms

• Computing
• Upper Secondary (Key Stage 4)
• GCSE

Year 11 refine Searching and sorting algorithms

Name all the searching algorithms you remember?

What is a linear search?

What is a binary search?

Using a linear search, how many searches will be performed to find 78?

1. 2
2. 8
3. 9
4. 4

Using a binary search, how many searches will be performed to find 78?

1. 2
2. 8
3. 9
4. 4

In your books or on Word:

• Draw the list and annotate it for a linear search
• Order the list to perform a binary search on it and annotate it for a binary search

no

no

no

no

yes

no

no

no

start + len[arr] // 2 (0 + 8 / 2 = 4), middle = 42, Del left half

start + len[arr] // 2 (5 + 8 // 2 = 6), middle = 74, Del left half

start + len[arr] // 2 (7 + 8 // 2 = 7), middle = 78, found 78

Total 3 searches

no higher

no higher

yes

What are the pros and cons of both algorithms? Write them in your books, then I will cold call using the random wheel.

Answers

i) 1 mark each bullet point, 3 total

• Compare to / pick out middle value (which is 6)
  
• Discard only left side // retain only right side (because 6 < 10)…
• Compare to / pick out (middle value which is) 10

ii) Data must be sorted / in order