Courses / Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course
2.2 Computational Thinking and Searching Algorithms
Unit 2 – Computational Thinking and Algorithms · 70 min read · 7 MCQs to check yourself
Computational thinking: what is it and how is it used?
1. Computational thinking
Computational thinking is a way of solving problems so that a computer (or a person) can carry out the solution. Its four pillars:
| Pillar | Meaning | Example: planning a school trip |
|---|---|---|
| Decomposition | Break a big problem into smaller, manageable parts | Transport, food, permission letters, budget |
| Pattern recognition | Find similarities/repeated patterns to reuse solutions | Every class needs the same permission letter – one template |
| Abstraction | Keep the important details, ignore the irrelevant ones | Bus route needs pick-up points and times, not the colour of the bus |
| Algorithm design | Write step-by-step instructions | Timetable of the day |
More examples: a map of the metro is an abstraction (shows stations and lines, not buildings); a calculator app hides how multiplication is done in binary (abstraction); a cricket scoring app is decomposed into batting, bowling and scoreboard modules.
2. Linear (sequential) search
Check each item from the start until the target is found or the list ends. Works on unsorted and sorted lists.
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i
return -1
cities = ["Quetta", "Lahore", "Karachi", "Peshawar", "Islamabad"]
print(linear_search(cities, "Peshawar"))
print(linear_search(cities, "Multan"))
Output:
3
-1
Worst case: n comparisons (target is last or missing). Best case: 1 comparison.
3. Binary search
Works only on a sorted list. Look at the middle item; if it is the target, stop; if the target is larger, search the right half, otherwise the left half. Each step halves the list.
def binary_search(items, target):
low, high = 0, len(items) - 1
steps = 0
while low <= high:
mid = (low + high) // 2
steps += 1
if items[mid] == target:
return mid, steps
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1, steps
data = [3, 8, 12, 17, 23, 31, 38, 45, 52, 60]
print(binary_search(data, 38))
print(binary_search(data, 5))
Output:
(6, 4)
(-1, 3)
Worst case: about ⌊ log₂ n ⌋ + 1 comparisons – for 1 000 000 items only 20 comparisons compared with up to 1 000 000 for linear search.
4. Which search should you use?
| Basis | Linear search | Binary search |
|---|---|---|
| Data must be sorted? | No | Yes |
| Method | Check items one by one | Repeatedly halve the search range |
| Worst-case comparisons | n | about log₂ n |
| Best for | Small or unsorted lists, data changing often, linked lists | Large sorted lists that are searched many times |
| Example | Finding a name in an unsorted attendance list | Finding a word in a dictionary, roll number in a sorted result list |
Model paper scenarios: bounded data ranges (values in a known, sorted range such as roll numbers 1–500) → binary search; small data sets → linear search (simple, sorting not worth it); large, sorted data sets → binary search (far fewer comparisons).
Linear search vs binary search
Linear vs binary search explained with visuals and Python code
Short and long questions
1. Define abstraction, decomposition and pattern recognition with one example each.
Model answer
Abstraction: focusing on essential details and hiding the rest – e.g. a metro map shows stations and lines only. Decomposition: breaking a problem into smaller parts – e.g. a school management system split into admissions, fees, attendance and results modules. Pattern recognition: spotting similarities to reuse a solution – e.g. calculating the area of many rectangles uses the same formula length × width.
2. Differentiate between linear search and binary search.
Model answer
| Linear search | Binary search |
|---|---|
| Works on sorted or unsorted lists | Needs a sorted list |
| Checks items one by one from the start | Checks the middle item and halves the range |
| Worst case n comparisons | Worst case about log₂ n comparisons |
| Simple, good for small lists | Fast for large lists |
3. Show the steps of binary search to find 38 in [3, 8, 12, 17, 23, 31, 38, 45, 52, 60].
Model answer
Step 1: low = 0, high = 9, mid = 4 → 23 < 38 → low = 5. Step 2: low = 5, high = 9, mid = 7 → 45 > 38 → high = 6. Step 3: low = 5, high = 6, mid = 5 → 31 < 38 → low = 6. Step 4: low = 6, high = 6, mid = 6 → 38 found at index 6. (4 comparisons instead of 7 for linear search.)
4. Write a Python function to perform linear search that returns the index of the item or −1.
Model answer
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i
return -1
Example: linear_search([4, 9, 2], 2) returns 2; linear_search([4, 9, 2], 7) returns −1.
5. Explain binary search with an algorithm/Python code and a worked example. Why is it more efficient than linear search and when can it not be used?
Model answer
Method: set low = 0 and high = n − 1; repeat while low <= high: mid = (low + high) DIV 2; if A[mid] = target, return mid; if A[mid] < target, low = mid + 1; else high = mid − 1. If the loop ends, the item is not present.
def binary_search(a, target):
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Example: find 23 in [3, 8, 12, 17, 23, 31, 38]: mid = 3 → 17 < 23 → low = 4; mid = 5 → 31 > 23 → high = 4; mid = 4 → 23 found at index 4 (3 comparisons). Efficiency: each comparison halves the range, so at most about log₂ n + 1 comparisons (20 for a million items) against n for linear search. Limitation: the list must be sorted (and allow direct access by index). For unsorted or very small lists, or lists that change constantly, linear search is used.
This lesson ends with a quiz of 7 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 2.1 Problem Solving: Algorithms, Pseudocode, Flowcharts and Tracing · Next: 2.3 Sorting Algorithms: Bubble Sort and Insertion Sort
All lessons in Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course