2.1 Comparing linear and binary searches

Question 1

binary search vs linear search

Answer 1

binary search is more efficient but the list has to be sorted

Question 2

best case scenario for linear and binary

Answer 2

linear: the search item is the first one (1 selection)
binary: the search item is the median (1 selection)

Question 3

worst case

Answer 3

linear: the search item is the last one (e.g. 500 with 500 selections)
binary: the search item is the last median selected (e.g. 10 selections in a list going up to 500)

Question 4

average case

Answer 4

linear: 500 + 1/2 = 250.5

(251 selections)

binary: 9 + 1/2 = 5

(6 selections)

Question 5

Describe one benefit and one drawback of using a binary search rather than a linear search [4]

Answer 5

a benefit of the binary search is that it uses a strategy to minimise the number of comparisons that are made and is therefore more effective than a linear search when there are a lot of items in a list

a drawback of using the binary search is that the list has to be ordered
sorting the data will take time and reduce the overall efficiency

Question 6

A student has the following names of friends stored in a list.

Alice, Ann, Claire, David, Mary, Matt, Peter, Stephen, Zoe

Show the stages of a binary search to find the name Ann in the above data [2]

Answer 6

the median item is ‘Mary’

the sub list to the left is selected

the median of this list is Ann, which is the search item