Following is a list of unsorted/unordered numbers: [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97,

Exercises · Q5

Q. Following is a list of unsorted/unordered numbers: [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55,9]

(a) Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required to find each of these numbers in the list.

(b) Use a Python function to sort/arrange the list in ascending order.

(c) Again, use linear search to determine the position of 1, 5, 55 and 99 in the list and note the number of key comparisons required to find these numbers in the list.

(d) Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required in each case.

Tripura TbseTextbookSubjective· 3mImportance★★★★★

71% · 12/17 Questions

🔒 Locked · start free trial →

You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.

Start your 14-day free trial to unlock the full solution →

Concept understanding — Linear Search

Imagine you have a stack of exam answer sheets on your desk, and you need to find the one belonging to a student named "Priya." You don't have them sorted alphabetically or by roll number. What do you do? You pick up the first sheet, check the name. Not Priya. You pick up the second, check. Not Priya. You keep going, one by one, until you either find Priya's sheet or reach the bottom of the pile.

That simple, step-by-step checking of each item in order is exactly what Linear Search is in computing. It is the most straightforward way to look for something in a list when you have no other information about how the list is arranged.

The Precise Meaning

In computer science, Linear Search (also called Sequential Search) is an algorithm that checks every element of a list, one after the other, from the beginning to the end, until the desired element is found or the list ends. There is no shortcut, no skipping ahead. It works on any list, whether the items are in order or completely jumbled.

Note

The NCERT textbook (Class 11, Computer Science, Chapter 6) introduces Linear Search as the simplest searching technique. It states that the algorithm "compares the element to be searched with each element of the list one by one" until a match is found or the list is exhausted. This is the exact definition you need for your exams.

Why It Matters

You might think, "Why not just sort the list first and then search faster?" That is a fair question, and it gets to the heart of why Linear Search is still taught and used.

It works on unsorted data. If you have a list of items that is constantly changing — like a live feed of stock prices or a list of new customer registrations — sorting it every time a new item is added is expensive and slow. Linear Search handles this chaos without complaint.
It is incredibly simple to understand and implement. For small lists (say, a list of 20 or 30 items), the difference between Linear Search and a faster method is negligible. The simplicity means there is almost no chance of a programming error.
It is the foundation. Understanding Linear Search teaches you the core idea of "iteration" — doing something repeatedly until a condition is met. This concept is the bedrock of almost every other algorithm you will learn.

The Key Trade-off …

Start your 14-day free trial to unlock the full solution →

This is a plain theory + code task question. It has four distinct sub-parts (a, b, c, d) that must each be answered completely.

(a) Linear search on the unsorted list

Linear search checks every element from the first position (index 0) until the target is found. The number of comparisons equals the position (1-based) where the element is found, or the full list length if absent.

Given list: [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]

1: Not present in the list. Comparisons = 24 (every element checked).
5: Found at index 12 (0-based). Comparisons = 13.
55: Found at index 22 (0-based). Comparisons = 23.
99: Found at index 20 (0-based). Comparisons = 21.

(b) Python function to sort the list in ascending order

def sort_list(arr):
    return sorted(arr)

unsorted = [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]
sorted_list = sort_list(unsorted)
print(sorted_list)

Output:

[5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]

The sorted() function returns a new list in ascending order. It uses Timsort (a hybrid sorting algorithm) internally.

(c) Linear search on the sorted list

Sorted list: [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]

1: Not present. Comparisons = 24.
5: Found at index 0. Comparisons = 1.
55: Found at index 11. Comparisons = 12.
99: Found at index 23. Comparisons = 24.

Sorting does not change the worst-case behaviour of linear search — it still checks sequentially. However, for elements that appear earlier in the sorted order (like 5), fewer comparisons are needed than in the unsorted case.

(d) Binary search on the sorted list

Binary search repeatedly divides the search interval in half. Each division is one iteration. The number of iterations is the number of times the list is halved until the element is found or the interval is empty.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    iterations = 0
    while low <= high:
        iterations += 1
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid, iterations
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, iterations

sorted_list = [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]
for target in [1, 5, 55, 99]:
    pos, iters = binary_search(sorted_list, target)
    print(f"{target}: position {pos}, iterations {iters}")

Output:

1: position -1, iterations 5
5: position 0, iterations 4 …

Start your 14-day free trial to unlock the full solution →

This question tests your understanding of linear search (unsorted vs sorted) and binary search (sorted only), comparing their efficiency through actual key comparisons and iterations.

The core idea here is simple: searching is about finding an element's position, and sorting makes certain searches dramatically faster. Linear search checks every element one by one — it doesn't care if the list is sorted or not. Binary search, on the other hand, only works on a sorted list and cuts the search space in half at every step.

Let's work through each part systematically.

(a) Linear Search on the Unsorted List

The given list is:

[50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]

Linear search works by starting at index 0 and moving forward until we find the target. The number of key comparisons equals the position (1-based) where the element is found — because we compare each element until we hit the target.

Let's trace each target:

For 1: The list has no element equal to 1. We compare all 24 elements and never find it. So position = "not found", comparisons = 24.

For 5: Starting from index 0: 50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, then 5 at index 12 (0-based). That's 13 comparisons (1-based position 13).

For 55: We scan: 50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, then 55 at index 22. That's 23 comparisons.

For 99: Scan: 50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, then 99 at index 20. That's 21 comparisons.

Watch out

Remember: position in the question likely means 1-based index (the element's place in the list, starting from 1). The 0-based index is one less. Always check what the question expects — here, "position" means 1-based.

(b) Python Function to Sort in Ascending Order

We'll write a clean function. Any sorting algorithm works — let's use Python's built-in sort() for reliability, but I'll also show a manual implementation to demonstrate understanding.

def sort_list(arr):
    # Using Python's built-in Timsort — efficient and correct
    arr.sort()
    return arr

# Alternatively, a manual bubble sort for teaching:
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Given list
numbers = [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]
sorted_numbers = sort_list(numbers.copy())  # copy to preserve original
print("Sorted list:", sorted_numbers)

Expected output:

Sorted list: [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]

Tip

Using arr.copy() is a good habit — it prevents the original list from being modified. In exams, always show that you understand the difference between mutating and returning.

(c) Linear Search on the Sorted List

Now the sorted list is:

[5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]

Linear search still checks from the start. Let's trace:

For 1: Not present. Compare all 24 elements. Comparisons = 24.

For 5: First element is 5. Found at position 1 (1-based). Comparisons = 1.

For 55: Scan: 5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, then 55 at position 12. Comparisons = 12.

For 99: Scan all the way to the end: 5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, then 99 at position 24. Comparisons = 24.

Note

| Target | Position (1-based) | Comparisons |

|--------|-------------------|-------------|

| 1 | Not found | 24 |

| 5 | 1 | 1 |

| 55 | 12 | 12 |

| 99 | 24 | 24 |

Notice that sorting helped 5 (found immediately) and 55 (found earlier than before), but 99 actually took more comparisons because it moved to the end. Linear search doesn't benefit from sorting in the worst case.

(d) Binary Search on the Sorted List

Binary search works by repeatedly dividing the search interval in half. We maintain low and high indices, compute mid, and compare. Each division is one iteration.

Let's trace each target on the sorted list (0-based indices 0 to 23):

For 1 (not present):

Iteration 1: low=0, high=23, mid=11 → value 55 > 1, so high=10
Iteration 2: low=0, high=10, mid=5 → value 31 > 1, so high=4
Iteration 3: low=0, high=4, mid=2 → value 17 > 1, so high=1
Iteration 4: low=0, high=1, mid=0 → value 5 > 1, so high=-1
low > high, stop. Not found. Iterations = 4.

For 5:

Iteration 1: low=0, high=23, mid=11 → 55 > 5, high=10
Iteration 2: low=0, high=10, mid=5 → 31 > 5, high=4
Iteration 3: low=0, high=4, mid=2 → 17 > 5, high=1
Iteration 4: low=0, high=1, mid=0 → 5 == 5, found at index 0. Iterations = 4.

For 55:

Iteration 1: low=0, high=23, mid=11 → 55 == 55, found at index 11. Iterations = 1.

For 99:

Iteration 1: low=0, high=23, mid=11 → 55 < 99, low=12 …

Start your 14-day free trial to unlock the full solution →

←Previous questionQ4 — Write a program that takes as input a list of 10 integers and a key va…→Next questionQ6 — Write a program that takes as input the following unsorted list of Eng…

Q.Following is a list of unsorted/unordered numbers: [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55,9]

(a) Linear Search on the Unsorted List

(b) Python Function to Sort in Ascending Order

(c) Linear Search on the Sorted List

(d) Binary Search on the Sorted List

🎓Unlock everything free for 14 days

Q.Following is a list of unsorted/unordered numbers:
[50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55,9]

Unlock everything free for 14 days