On this page
Searching and sorting are the first algorithms where you can watch efficiency happen. The same task, finding a number in a list, can take a thousand steps or ten, depending on the method. This post traces linear search, binary search and bubble sort by hand with real numbers, gives short Python versions, and points out where students lose marks.
Where are these in the CBSE syllabus?
The CBSE Computer Science curriculum for 2026-27 lists "linear search on list of numbers" and on tuples among the suggested Class 11 programs, and "search for a given element in the list/tuple" in the practical list. The Class 12 syllabus for that year does not list sorting or binary search. The NCERT Class 12 textbook still has full chapters on Sorting and Searching, and the algorithms are worth knowing for your practical file and for any programming beyond school. Check the curriculum for your year and ask your teacher what will be assessed.
Why trace algorithms by hand?
Reading code and predicting what it does is a separate skill from writing it, and many students lack it. A study across seven countries, Lister and colleagues (2004), tested students at the end of their first programming course on predicting the output of short pieces of code and on picking the right line to complete near-finished code. Many were weak at both, especially the second, which suggests a fragile grasp of the basics that problem-solving depends on. Tracing searches and sorts by hand builds exactly that grasp.
How does linear search work?
Start at the first item and compare each one with the key until you find it or run out of items.
def linear_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i
return -1For the list [3, 8, 12, 17, 23, 31, 42, 56] and key 31, the loop compares 3, 8, 12, 17, 23 and then 31: six comparisons, returning index 5. If the key is missing, it makes all eight comparisons and returns −1. In the worst case, linear search makes n comparisons for n items. It works on any list, sorted or not.
How does binary search work?
Binary search needs a sorted list. Compare the key with the middle item. If they match, stop. If the key is larger, throw away the left half; if smaller, the right half. Repeat.
def binary_search(lst, key):
first, last = 0, len(lst) - 1
while first <= last:
mid = (first + last) // 2
if lst[mid] == key:
return mid
elif lst[mid] < key:
first = mid + 1
else:
last = mid - 1
return -1Trace for key 31 in the same list:
first = 0, last = 7, mid = 3. lst[3] = 17, which is less than 31, so first = 4.
first = 4, last = 7, mid = 5. lst[5] = 31. Found at index 5.
Two comparisons instead of six.
Trace for a missing key, 10:
mid = 3, lst[3] = 17 > 10, so last = 2.
first = 0, last = 2, mid = 1, lst[1] = 8 < 10, so first = 2.
first = 2, last = 2, mid = 2, lst[2] = 12 > 10, so last = 1.
Now first > last, so the loop ends and the function returns −1.
Because each step halves the search area, the worst case for n items is about log₂ n comparisons. Since 2¹⁰ = 1,024, at most 10 comparisons find any item in a sorted list of 1,000, where linear search might need 1,000.
How does bubble sort work?
Bubble sort compares neighbouring items and swaps them if they are in the wrong order. After each pass, the largest remaining item has "bubbled" to the end. NCERT notes that a list of n items needs at most n − 1 passes.
def bubble_sort(lst):
n = len(lst)
for i in range(n - 1):
for j in range(n - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]Trace for [5, 1, 4, 2, 8]:
Pass 1: (5, 1) swap, (5, 4) swap, (5, 2) swap, (5, 8) no swap. Result [1, 4, 2, 5, 8].
Pass 2: (1, 4) no swap, (4, 2) swap, (4, 5) no swap. Result [1, 2, 4, 5, 8].
Pass 3: (1, 2) no swap, (2, 4) no swap. No change.
Pass 4: (1, 2) no swap.
Comparisons: 4 + 3 + 2 + 1 = 10, which is n(n − 1)/2 for n = 5. The list was already sorted after pass 2. A common improvement keeps a flag and stops when a pass makes no swaps; here that would stop after pass 3, with 9 comparisons. NCERT explains that a loop inside a loop, as here, makes bubble sort a quadratic-time algorithm.
Which mistakes cost marks?
Running binary search on an unsorted list. It may return −1 for an item that is there. Sort first, or use linear search.
Writing `while first < last`. This skips the case where one item is left, so the last trace above would end a step early.
Forgetting `// 2`. A single `/` gives a float, which cannot be a list index.
Off-by-one in the inner loop. Without the −1 in `range(n - 1 - i)`, `lst[j + 1]` goes past the end and raises an IndexError.
Counting passes instead of comparisons when the question asks for comparisons.
In real programs, use Python's built-in `sorted()` and `list.sort()`. The Python sorting guide explains that they use an algorithm called Timsort, which takes advantage of any order already in the data, and notes that its sorts are stable: items that compare equal keep their original order. Learn the hand-written versions to understand how they work, then use the built-ins in projects.
A practice routine
Write a sorted list of 15 numbers. Trace binary search for one present key and one missing key, using the table format.
Trace bubble sort on a 6-item list in reverse order, which is the worst case, and confirm that it takes 15 comparisons.
Type all three functions from memory, test them on your lists, and compare with your traces.
Add a swap flag to bubble sort and count how many passes it saves on a nearly sorted list.
If a trace keeps going wrong at the same step, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. Searching connects to the next data structure in Class 12, covered in our post on stacks in Python.
Today, trace binary search for 42 in the list above and check your table against the code.
