QUESTION 17 · Searching

What does linear search do when values are unsorted?

2 marks

Answer

It compares the key with successive elements until a match is found or the list ends.

Sorting is not required.
This implementation returns the first matching zero-based index, or -1 when absent.

Explain linear search and write a non-recursive C function to implement it.

5 marks

Answer in brief

Linear search checks elements one by one for a required key. It works on both sorted and unsorted arrays.

Algorithm

Start at index 0.
Compare a[i] with key. Return i if equal.
Otherwise move to the next element.
If every element has been checked, return -1.

Worked trace

For 8, 3 and 5 with key 3, index 0 does not match. Index 1 matches, so the function returns 1. The displayed result is an index, not a one-based position. If the key were 7, all three comparisons would fail and -1 would be returned.

Duplicates and boundaries

Returning immediately at a match produces the first matching index. A one-element list is checked once. A generic linear-search function can also handle a length of zero by skipping its loop, although this interactive sample requires at least one input element.

Time complexity

The best case is a match at index 0, requiring one comparison: O(1). In the worst case, the key is absent or appears only at the last element, requiring n comparisons: O(n). Under a usual equally-likely-position model, successful average search also grows linearly. The input-reading part of the complete program is O(n) regardless of where a match occurs.

Space complexity

The non-recursive search stores only an index and fixed parameters, so auxiliary space is O(1). It neither sorts nor copies the input array.

Diagram or flowchart

Explain linear search and write a non-recursive C function to implement it. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int linear_search(const int a[], int n, int key)
{
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) { return i; }
    }
    return -1;
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    int key;
    if (scanf("%d", &key) != 1) { puts("Unsupported input"); return 1; }
    printf("Index = %d\n", linear_search(a, n, key));
    return 0;
}

Sample input and output

Input

3
8 3 5
3

Output

Index = 1