Tracing binary search: Class 12 practice

What you should know first

• Lists and indexes

The idea behind tracing binary search

Binary search works on a sorted list: compare the target with the middle element, then keep only the half that can contain it. Each step halves the search space, so at most ⌊log₂ n⌋ + 1 comparisons are needed.

Step-by-step method

1. Set low = 0, high = n − 1.
2. mid = (low + high) // 2; compare list[mid] with the target.
3. Move low or high past mid and repeat until found or low > high.

Worked example 1 (Basic)

Binary search for 18 in [18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58]. Which middle values are compared, and how many comparisons are made?

1. Middle values: 38 → 26 → 18
2. Found at index 0
3. 3 comparisons
4. Answer: 38 → 26 → 18; 3 comparisons, index 0

Worked example 2 (Standard)

Binary search for 28 in [20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48]. Which middle values are compared, and how many comparisons are made?

1. Middle values: 34 → 26 → 30 → 28
2. Found at index 4
3. 4 comparisons
4. Answer: 34 → 26 → 30 → 28; 4 comparisons, index 4

Worked example 3 (Challenge)

Binary search for 18 in [17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71]. Which middle values are compared, and how many comparisons are made?

1. Middle values: 44 → 29 → 20 → 17
2. low > high: not found
3. 4 comparisons
4. Answer: 44 → 29 → 20 → 17; 4 comparisons, not found

Common mistakes and misconceptions

• Using it on an unsorted list
• Forgetting integer division for mid

Practice questions

1. (Basic) Binary search for 12 in [12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72]. Which middle values are compared, and how many comparisons are made?
2. (Basic) Binary search for 22 in [16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]. Which middle values are compared, and how many comparisons are made?
3. (Standard) Binary search for 35 in [20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62]. Which middle values are compared, and how many comparisons are made?
4. (Standard) Binary search for 16 in [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43]. Which middle values are compared, and how many comparisons are made?
5. (Challenge) Binary search for 42 in [17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89]. Which middle values are compared, and how many comparisons are made?
6. (Challenge) Binary search for 36 in [15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69]. Which middle values are compared, and how many comparisons are made?

Answer key with full working

• Q1: Middle values: 42 → 24 → 12 → Found at index 0 → 3 comparisons → Answer: 42 → 24 → 12; 3 comparisons, index 0
• Q2: Middle values: 26 → 20 → 22 → Found at index 3 → 3 comparisons → Answer: 26 → 20 → 22; 3 comparisons, index 3
• Q3: Middle values: 41 → 29 → 35 → Found at index 5 → 3 comparisons → Answer: 41 → 29 → 35; 3 comparisons, index 5
• Q4: Middle values: 22 → 10 → 16 → Found at index 5 → 3 comparisons → Answer: 22 → 10 → 16; 3 comparisons, index 5
• Q5: Middle values: 53 → 33 → 41 → 45 → low > high: not found → 4 comparisons → Answer: 53 → 33 → 41 → 45; 4 comparisons, not found
• Q6: Middle values: 42 → 27 → 33 → 36 → Found at index 7 → 4 comparisons → Answer: 42 → 27 → 33 → 36; 4 comparisons, index 7

Syllabus note

This skill is listed under "Searching" for Class 12 in the NCERT/CBSE books. ICSE, IGCSE, IB and state boards may teach it in a different chapter or year.

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.

Related practice and notes

• Dictionary operations
• SQL aggregate functions
• Stack operations
• Queue operations
• All Class 12 practice

Frequently asked questions

Which chapter is tracing binary search in?

"Searching", Class 12 Computer Science (NCERT/CBSE). Other boards may place it differently.

How were the answers checked?

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.