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