Quelpr
2 marksSearching and Sorting Algorithms

CAPE Computer Science Unit 2 · 2013 · Paper 2 · Question 2(d)(ii)

Given an array containing 16 sorted integers: [1, 5, 7, 15, 19, 23, 24, 28, 31, 36, 54, 57, 67, 72, 79, 80].

How many comparisons does a binary search make before determining that 50 is not present in the array? Show your working.

This question uses a figure or table from the paper — you'll see it when you practise.

The mark scheme is shown once you've answered.

Practise this question

Other parts of this question

  1. 2(a)(i)Explain the purpose of the outer 'for' loop.[2 marks]
  2. 2(a)(ii)Explain carefully the process occurring in the inner 'for' loop.[3 marks]
  3. 2(a)(iii)State why the upper limit for j in the inner 'for' loop is (numItems - i) rather than (numItems).[1 mark]
  4. 2(a)(iv)a)Given the array a with 5 values: [5, 1, 4, 8, 2], show the contents of the array after each stage during the FIRST pass of the bubble sort.[4 marks]
  5. 2(a)(iv)b)Show the contents of the array at the end of the SECOND and THIRD passes of the bubble sort.[2 marks]
  6. 2(b)An array contains 7 integers: [34, 5, 10, 1, 9, 23, 14]. Using the selection sort algorithm, show the array contents after each of the first four passes.[4 marks]
  7. 2(c)Describe the principles behind binary search when searching for an item in an array.[6 marks]
  8. 2(d)(i)How many comparisons does a linear search make before determining that 50 is not present in the array?[1 mark]

More practice: the rest of this paper · more Searching and Sorting Algorithms questions · all CAPE Computer Science Unit 2 past papers