An algorithm that compares the value being looked for with each item in turn, starting at the first item
What is meant by a binary search?
An algorithm that checks the middle item of a sorted list, then throws away the half that cannot hold the value
What is the name for a condition that must already be met before an algorithm can be used, such as the data being in order before a certain search can be carried out?
Pre-requisite
What is meant by mid in a binary search?
The position of the middle item of the part of the list that is still being searched
Which term describes one check in which a search algorithm compares the value it is looking for with a single item in a list?
Comparison
What is meant by a sorted list?
A list in which the items are arranged in numerical or alphabetical order
In a binary search, what do the variables low and high hold?
The positions of the first and last items of the part of the list still being searched
What is the main purpose of a search algorithm?
To find whether an item is in a list and where it is
What is a pre-requisite of a binary search that a linear search does not have?
The list must already be sorted into order
A linear search is used to find 30 in the list 5, 12, 18, 24, 30, 36, 42. How many comparisons are made before 30 is found?
5
A linear search compares every item in a list and finds no match. What does this mean?
The item being searched for is not in the list
A binary search is used on the sorted list 4, 9, 15, 22, 28, 31 (positions 0 to 5). Which item is compared first?
15
In a binary search, the item being looked for is larger than the middle item. What happens next?
The middle item and everything before it are discarded
A binary search is looking for a value that is not in the list. How does the search finish?
When low becomes greater than high, so there is nothing left
Why does a binary search usually make fewer comparisons than a linear search on a large sorted list?
Each comparison removes half of the items still to be checked
A search uses low, high and mid, sets mid to (low + high) // 2 and moves low or high past mid. Which search is this?
Binary search
A list of names is stored in no particular order and will be searched once. Which search is the better choice?
A linear search, because the list is not sorted
A binary search is used on the sorted list 1, 3, 5, 7, 9, 11, 13, 17, 23, 29 (positions 0 to 9) to find 23. How many comparisons are made before 23 is found?
3
A binary search is used on the sorted list 1, 8, 16, 17, 18, 19, 25 (positions 0 to 6) to look for 20. How many comparisons are made before the search stops?
3
A program searches a list using a single index that starts at 0 and goes up by 1 each time round a loop, comparing the item at that index with the value it wants until the item is found or the end of the list is reached. Which search is the program using?
Linear search
A binary search is used on the sorted list butterscotch, chocolate, mint, strawberry, vanilla (positions 0 to 4) to look for chocolate. Which item is compared second?
Butterscotch
In search algorithms, what is the usual name for the value that the algorithm is trying to find in a list?
Target
A linear search is used to find 50 in the list 5, 12, 18, 24, 30, 36, 42. How many comparisons are made before the search finishes?
7
A programmer adds a new score to the end of a sorted list but does not sort the list again. Why might a binary search now give the wrong result?
The list is no longer fully sorted, so the search could discard the half that actually contains the value
We use cookies to enhance your experience. You can manage your preferences or learn more in our Cookie Policy.