Search Algorithms Exam Questions

• D Discards the second half of the array (1)
• The only correct answer is D. The correct answer is discards the second half of the array.
• A is not correct because checking each item from the start of the array is how a linear search works, not a binary search
• B is not correct because the target value is smaller than the mid-point, so it must be in the first half, which is kept and searched again
• C is not correct because the mid-point has already been compared and is not the target, so it is discarded along with the second half

• C Linear search (1)
• The only correct answer is C. The correct answer is linear search.
• A is not correct because a binary search repeatedly halves the array and discards one half
• B is not correct because a bubble sort compares and swaps pairs of items to put them in order
• D is not correct because a merge sort divides the array into smaller arrays and merges them

• C 12 (1)
• The only correct answer is C. The correct answer is 12.
• A is not correct because 1 comparison would only be made if the target were the first item, and here every item must be checked
• B is not correct because 11 is the index of the last item in an array of 12 items, not the number of comparisons
• D is not correct because 13 is more than the number of items, and a linear search compares each item once

Award one mark for any of the following up to a maximum of two marks:

• Starts at the first item/the beginning of the list/array/first element/index 0 (1)
• Compares each item/element with the target/search value, one item at a time/in turn (1)
• Stops when the target/search value is found (1)
• Stops when the end of the list/array is reached without the target being found/and reports that the value is not in the list (1)
• The list does not need to be sorted/can be used on an unsorted list (1)

Do not accept 'it splits/halves the list', which describes a binary search

Do not accept 'it looks through the list'/'it searches every item' without a comparison to the target

Award one mark for any of the following up to a maximum of two marks:

• The mid-point/middle item of the array (or of the remaining items) is found (1)
• The target/search value is compared with the value at the mid-point/middle item (1)
• The half (of the array) that cannot contain the target is discarded/ignored/not searched (1)
• The search is repeated on the remaining half/the half that is left (1)

Do not accept 'the array is split and both halves are searched'

Do not accept 'it checks every item until the target is found', which describes a linear search

Award one mark for any of the following up to a maximum of two marks:

• The number of comparisons made (1)
• The number of passes through a loop/iterations (1)
• The amount of memory used/use of memory (1)
• The time taken to run/number of operations (1)

Do not accept the number of items in the array/list, the programming language used or the number of lines of code

Award up to two marks for a linked description such as:

• Finds/examines the middle item/name (in the list) (1) and compares it with the name/target being searched for (1)
• If the name/target comes before the middle item (alphabetically) (1) the middle item and the upper/later half of the list are discarded / the search continues on the lower/earlier half (1)
• If the name/target comes after the middle item (alphabetically) (1) the middle item and the lower/earlier half of the list are discarded / the search continues on the upper/later half (1)
• The middle item of the remaining half is found and compared with the name/target (1) so the process repeats until the name is found or no items are left (1)

Allow 'checks/looks at the middle name' for the middle item mark, but the comparison mark needs a reference to the name/target being searched for.

Allow a candidate who says the half is discarded and then says the search repeats on the remaining half to gain both marks, e.g. 'the upper half is discarded (1) then the search is repeated on the lower half (1)'.

Accept the lower/earlier half or the upper/later half being kept instead of discarded, e.g. 'it now only searches the lower half (1)'.

Do not award the end condition (name found / no items left) as the second mark for the middle item point, as it is not a development of the comparison.

Allow 'splits the list in half' for finding the middle item (1), but not for the discard mark, as it does not say which items are discarded.

Ignore 'divide and conquer' on its own, as it does not describe what is compared or discarded.

Do not accept descriptions of a linear search, such as starting at the first name and checking each name in turn.

Award up to two marks for a linked description such as:

• Compares the target (product code) with each item/product code in the (unsorted) list (1) from the first item to the last (1)
• Checks/compares every item in the list (1) and if none of them is a match, the code is not in the list (1)
• Reaches the end of the list (1) without finding a match, so reports/decides that the product code is not in the list (1)
• Keeps looping/iterating through the list to the end (1) because a code that is not in the list never produces a match (1)

Allow 'checks every item' on its own for one mark (the comparison of each item), but not the second mark without the end-of-list/not found decision.

Do not accept answers that check the middle item or discard half of the list; that describes a binary search.

Do not award credit for 'stops/it stops when it finds the code' on its own, as this does not show how the search decides the code is not in the list.

Award up to two marks for a linked description such as:

• A binary search checks the middle item first (1) then discards the half of the list that cannot contain the target (1)
• A binary search halves/discards half of the remaining items after each comparison (1) so it makes fewer comparisons than a linear search (1)
• A linear search checks items one by one (1) whereas a binary search discards half of the remaining items each time (1)
• A linear search may have to compare the target with every item in the list (1) whereas a binary search removes half of the remaining items after each comparison (1)
• For a large sorted list, a binary search needs far fewer comparisons (1) because each comparison eliminates half of the remaining items (1)

Allow 'checks the halfway point/middle item first' for the discarding mechanism.

Allow 'half the list is eliminated/removed/discarded each time' as the linked development.

Do not accept 'binary search uses less memory' or 'binary search is faster because the list is sorted' unless it refers to the number of comparisons/items checked.

Do not award a mark for simply saying one algorithm is faster or better.

A halving/discard point on its own earns one mark only if it is stated as a step that removes part of the list.

Award up to two marks for a linked explanation such as:

• Binary search halves/discards half of the remaining items after each comparison (1) so only a small number of items need to be compared before it can decide the target is not in the array (1)
• Binary search checks the middle item and discards one half (1) so it does not compare the target with every item in the array before deciding it is not there (1)
• Binary search halves the number of items still to be searched with each pass (1) so its maximum number of comparisons is far fewer than the number a linear search makes to reach the end of the array (1)
• A linear search must compare the target with every item in the array to decide it is not there (1) whereas a binary search discards half of the items each time so makes far fewer comparisons (1)

For both marks, the expansion must follow/associate with the statement.

A statement that a binary search halves/discards half of the items on its own, with no linked reason about fewer items/comparisons being checked, earns one mark only.

Do not accept 'binary search is faster/quicker' or 'binary search is more efficient' on its own without saying that fewer items/comparisons are checked.

Do not accept answers about sorting the array; the question asks about searching an array that is already sorted.

Award up to two marks for a linked explanation such as:

• A binary search compares the target with the middle item and discards one half of the array (1) because in an unsorted array the target could be in the half that is discarded (1)
• A binary search uses the order of the items to decide which half to keep searching (1) so in an unsorted array it may keep the wrong half and miss the target (1)
• The middle item is only a reliable split point when the array is sorted (1) so in an unsorted array the search may discard the half that contains the target (1)

For both marks, the expansion must follow/associate with the statement.

Allow 'discard the wrong half' / 'it might miss the item' / 'it may skip over the target' as the linked reason (1) when it follows a statement about discarding/choosing a half.

Do not accept 'it needs to be sorted' / 'it only works on sorted data' on its own without saying what goes wrong, e.g. that the target may be discarded/missed.

Do not accept answers about speed, e.g. that a linear search is slower/faster; the question asks why a binary search cannot be used.

Award up to two marks for a linked explanation such as:

• The first item checked matches the target (1) so the search stops (after one comparison) (1)
• Only one comparison/item is needed (1) so the rest of the array does not have to be checked (1)
• The search ends as soon as the first comparison is made (1) because the item at index 0 is the target (1)
• No further passes through the array are needed (1) because the target is found at the first position/index 0 (1)

For both marks, the expansion must follow/associate with the statement.

Do not accept 'it is fast' or 'it finds it quickly' without saying that only one comparison/item is checked or that the search stops.

Do not accept 'it finds the target' or 'the search stops when it finds the target' on its own, without saying that this happens at the first item/after one comparison.

Indicative content

How a linear search finds a product code

• The search starts at the first code in the list and compares it with the code the customer entered.
• It then moves to the next code in the list and repeats the comparison until it finds the code that matches.
• It stops when the code is found, or when it reaches the end of the list without a match, which shows the code is not in the list.
• It works on the list as it is, so the shop would not have to change the way the codes are stored.
• A code near the end of the list, or a code that is not in the list at all, means every code is compared, so on a long list this search takes a long time.

How a binary search finds a product code

• It compares the code the customer entered with the middle code in the sorted list.
• If the wanted code comes after the middle code alphabetically, the middle code and the lower half of the list are discarded.
• If the wanted code comes before the middle code alphabetically, the middle code and the upper half of the list are discarded.
• It repeats this with the middle code of the half that is left, so the number of codes still being searched is halved at each step.
• It stops when the code is found, or when there are no codes left to search, which shows the code is not in the list.
• On a long list it needs far fewer comparisons than a linear search, because the half that is not needed is never searched.

Changes the shop would need to make

• The list of codes would have to be sorted before a binary search could be used.
• Each new product code would have to be inserted into the correct place in the list, or the whole list re-sorted, whenever codes are added or removed.
• Keeping the list in order is extra work for the shop every time its codes change, which an unsorted list does not need.
• The shop would need to judge whether that extra work is outweighed by the faster searches the website would get.

Levels

• Level 0 (0 marks): No rewardable content.
• Level 1 (1–2 marks): Basic, independent points are made, showing elements of understanding of key concepts/principles of computer science. (AO1) The discussion will contain basic information with little linkage between points made or application to the context. (AO2)
• Level 2 (3–4 marks): Demonstrates adequate understanding of key concepts/principles of computer science. (AO1) The discussion shows some linkages and lines of reasoning with some structure and application to the context. (AO2)
• Level 3 (5–6 marks): Demonstrates comprehensive understanding of key concepts/principles of computer science to support the discussion being presented. (AO1) The discussion is well developed, with sustained lines of reasoning that are coherent and logically structured, and which clearly apply to the context. (AO2)

Level 3 responses must describe how both searches work, including which half is discarded and when each search stops, and must cover the work of keeping the list sorted.

Do not accept a binary search that picks items at random, removes one item at a time, or works on a list that is not sorted.

Indicative content

Number of comparisons

• A linear search may compare the stock code with all 50,000 codes, which is the worst case when the code is last or not in the array.
• The best case for a linear search is one comparison, when the first code matches.
• A binary search compares the target with the middle code, then with the middle of the half that is left, so the number of codes still to check is halved each time.
• 50,000 codes need at most about 16 comparisons in a binary search, because 2^16 is 65,536, which is far fewer than a linear search.
• Fewer comparisons means each stock check is answered more quickly, which matters because the warehouse carries out many checks in a day.

Number of passes through the loop

• Each pass of the loop in the linear search checks one code, so one search can need up to 50,000 passes.
• Each pass of the loop in the binary search discards about half of the remaining codes, so the loop runs about 16 times at most.
• The array is not in order, so it would have to be sorted before every binary search, and a sort such as bubble sort makes many passes over all 50,000 codes itself.
• Because codes are added and removed during the day the array will not stay sorted, so the sorting work would be repeated and could outweigh the saving in the search.

Use of memory

• Both searches work on the array already in memory and need only a few variables, such as the target and an index counter.
• A binary search also needs variables for the start, end and mid-point indexes, so it uses slightly more memory than a linear search.
• Some sorts, such as merge sort, need a second array to hold the merged lists, which needs extra memory for another 50,000 codes.
• If memory is limited, the linear search on the array as it is avoids needing a sorted copy of the data.

Levels

• Level 0 (0 marks): No rewardable content.
• Level 1 (1–2 marks): Basic, independent points are made, showing elements of understanding of key concepts/principles of computer science. (AO1) The discussion will contain basic information with little linkage between points made or application to the context. (AO2)
• Level 2 (3–4 marks): Demonstrates adequate understanding of key concepts/principles of computer science. (AO1) The discussion shows some linkages and lines of reasoning with some structure and application to the context. (AO2)
• Level 3 (5–6 marks): Demonstrates comprehensive understanding of key concepts/principles of computer science to support the discussion being presented. (AO1) The discussion is well developed, with sustained lines of reasoning that are coherent and logically structured, and which clearly apply to the context. (AO2)

Level 3 responses must weigh the saving in comparisons against the cost of sorting the array, not describe only one search.

Do not accept a binary search being quicker on the unsorted array, or memory use being described as the search storing a copy of every code it compares.