2.1 Binary search

Question 1

binary search

Answer 1

compares the search item with the median item in a list, repeatedly splitting the list in half until the item is found or there are no more items left to search

Question 2

process of using a binary search

Answer 2

the list must have already been ordered

• select the median
• compare it with the search item
• if the search item is lower, discard the median and higher items
• if the search item is higher, discard the median and lower items
• recalculate the median
• repeat until the search item is found/not found in the list

Question 3

median values

Answer 3

the median is the middle item in the list (e.g. in a list of 13 it is the 7th item)

if there is an even number of numbers, the one to the right of the median can be used (e.g. in a list of 10 the 6th item)

lists of numbers need to be in numerical order

list of words need to be in alphabetical order

Question 4

Numbers have been written onto 11 cards that have then been placed face down in ascending order.
Show the stages in a binary search to see if the number 28 is one one of the cards. [4]

Answer 4

the median card is selected and turned over

one half of the cards are discarded based on if the number is higher or lower than the current card

the new median is selected

the process is repeated until the number is found/not found

Question 5

Describe the stages in applying a binary search to the following list to find the number 17

3, 5, 9, 14, 17, 21, 27, 31, 35, 37, 39, 40, 42 [4]

Answer 5

the median item is 27 but this is higher than the search item

the sub-list to the left is used - 3, 5, 9, 14, 17, 21

the median is 9 but this is lower than the search item

the sub-list to the right is used - 14, 17 and 21

the median is 17 which is the search item