AmbifulWorksheets
Practice that never repeats
CBSE · Class 9 · Computational Thinking and AI

Searching and Sorting

Standard difficulty · 20 questions · 40 marks · Time: 37 minutes

Name: Date: Score: ____ / 40

Show your working for Sections B and C. Answers are on the last page — try every question first!

Section A — Choose the correct answer8 × 1 = 8 marks
1.
Binary search can be used only when the list is:
  1. made of even numbers
  2. unsorted
  3. short
  4. sorted
2.
Linear search checks the items one by one from the left. How many items are checked when searching 77, 80, 72, 54, 74, 71, 94, 63, 97 for 58?
  1. 5
  2. 8
  3. 9
  4. 10
3.
Binary search: number the positions 1, 2, 3, …; check the middle position (the whole part of (low + high) ÷ 2); if the target is smaller, search the left half, if larger, the right half. How many items are checked when searching 2, 13, 27, 37, 41, 51, 58, 63, 87, 88 for 51?
  1. 4
  2. 3
  3. 2
  4. 6
4.
Bubble sort: in each pass, compare neighbours from left to right and swap any pair in the wrong order. What is the list 47, 22, 6, 36, 35, 19 after 2 passes?
  1. 47, 22, 6, 36, 35, 19
  2. 6, 35, 22, 19, 36, 47
  3. 6, 19, 22, 35, 36, 47
  4. 6, 22, 35, 19, 36, 47
5.
Selection sort: in each pass, find the smallest item in the unsorted part and swap it to the front of that part. What is 24, 30, 28, 6, 26, 38 after 3 passes?
  1. 6, 24, 26, 30, 28, 38
  2. 6, 24, 26, 30, 38, 28
  3. 6, 24, 30, 26, 28, 38
  4. 6, 24, 26, 28, 30, 38
6.
In the first pass of bubble sort on 26, 34, 17, 27, 37, 31, 33, how many swaps are made?
  1. 5
  2. 7
  3. 3
  4. 4
7.
A sorted list has 1,578 items. What is the greatest number of items binary search may need to check?
  1. 789
  2. 10
  3. 11
  4. 12
8.
For a sorted list of 1,485 items, how many more checks can linear search need than binary search, in the worst case?
  1. 11
  2. 1,474
  3. 1,485
  4. 1,475
Section B — Short answer8 × 2 = 16 marks
9.
Why must a list be sorted before binary search?
10.
Bubble sort compares neighbours from left to right in each pass, swapping any pair in the wrong order. Write 31, 57, 15, 55, 8, 41 after 3 passes, separated by commas.
11.
Selection sort swaps the smallest item of the unsorted part to its front in each pass. Write 30, 44, 31, 46, 35, 17 after 3 passes, separated by commas.
12.
Binary search: number the positions 1, 2, 3, …; check the middle position (the whole part of (low + high) ÷ 2); if the target is smaller, search the left half, if larger, the right half. Searching 26, 35, 38, 40, 52, 56, 62, 65, 71, 83, 86, 90 for 26, which numbers are checked? Write them in order.
13.
Linear search checks 20, 84, 77, 59, 67, 63, 47, 26 from the left. How many items are checked to search for (a) 67 (b) 97?
14.
Bubble sort swaps neighbouring items that are in the wrong order. How many swaps in all does it make to sort 52, 28, 36, 43, 3, 54?
15.
A bubble sort stops after the first pass that makes no swaps. How many passes does it make for 19, 21, 30, 52, 7, 29, counting that last pass?
16.
What is the greatest number of checks binary search needs for a sorted list of 4,230 items?
Section C — Word problems4 × 4 = 16 marks
17.
Explain binary search step by step for finding 23 in 4, 8, 15, 16, 23, 42, 50.
18.
Binary search: number the positions 1, 2, 3, …; check the middle position (the whole part of (low + high) ÷ 2); if the target is smaller, search the left half, if larger, the right half. The list is 9, 13, 24, 25, 35, 48, 55, 58, 62, 64, 84, 94, 96 and the target is 62. (a) Which numbers are checked, in order? (b) How many checks is that? (c) How many checks would linear search from the left need?
19.
Sort 38, 35, 54, 6, 40, 51 with bubble sort. (a) Write the list after pass 1. (b) after pass 2. (c) How many swaps does the whole sort make?
20.
Sort 13, 16, 8, 40, 3, 49, 35 with selection sort. (a) Write the list after pass 1. (b) after pass 2. (c) How many passes does selection sort need for 7 items?
AmbifulWorksheets
Practice that never repeats
CBSE · Class 9 · Computational Thinking and AI

Answer key

Searching and Sorting · AW-9CT-SSO-2026-V1 · For parents — fold back or tear off before handing the sheet to your child.

QAnswerWorking
1(d) sorted—
2(c) 958 is not there, so all 9 are checked
3(b) 3checked: 41, 63, 51
4(d) 6, 22, 35, 19, 36, 47each pass carries the largest remaining number to its place
5(a) 6, 24, 26, 30, 28, 38the 3 smallest go to the front, in order
6(d) 4list after the pass: 26, 17, 27, 34, 31, 33, 37
7(c) 11halving 1,578 until one item is left: 210 ≤ 1,578 < 211
8(b) 1,474linear: 1,485; binary: 11; 1,485 − 11
9Binary search throws away the half that cannot hold the target; that only works if smaller items are on one side and larger on the other.—
1015, 8, 31, 41, 55, 57swaps per pass: 4, 3, 1
1117, 30, 31, 46, 35, 44one item fixed per pass
1256, 38, 263 checks
13(a) 5; (b) 897 is not in the list, so every item is checked
147every swap fixes one out-of-order pair; count those pairs
155swaps per pass: 2, 2, 1, 1, 0
1613212 ≤ 4,230 < 213
17Middle (4th) is 16; 23 is larger, so search 23, 42, 50; middle is 42; 23 is smaller, so search 23; found in 3 checks.—
18(a) 55, 64, 58, 62; (b) 4; (c) 9linear: 62 is item 9
19(a) 35, 38, 6, 40, 51, 54; (b) 35, 6, 38, 40, 51, 54; (c) 6swaps in pass 1: 4
20(a) 3, 16, 8, 40, 13, 49, 35; (b) 3, 8, 16, 40, 13, 49, 35; (c) 6after n − 1 passes the last item is already in place