Linear search with a non-recursive function

THE SYLLABUS QUESTION

What you need to solve

Write a C program that uses a non-recursive function to search for a Key value in a given list of integers using linear search method.

Input format & conventions

Array size n (1–100), then n integers (-1,000,000 to 1,000,000), then the key. The list need not be sorted. Output is the first 1-based position, or -1.

UNDERSTAND THE IDEA

Explanation

Linear search checks values one at a time from the beginning. It works on either sorted or unsorted input.

The non-recursive function returns a zero-based index on the first match and -1 otherwise. main converts an index into a 1-based position for display.

PLAN BEFORE CODING

Algorithm

Read the array and key.
Call linearSearch.
Compare each element with the key.
Return its index immediately on a match, or -1 after the loop.
Display the first matching position or -1.

SEE THE CONTROL FLOW

Flowchart

Follow the arrows from Start. Diamonds ask a question; labeled arrows show the answer. A returning arrow repeats a loop. Function internals are grouped where needed; later input checks follow the rules in the program.

On a phone, scroll sideways to read the diagram at full size. Open full-size flowchart ↗

#include <stdio.h>
#define MAX_SIZE 100

int readArray(int a[], int *n) {
    if (scanf("%d", n) != 1 || *n < 1 || *n > MAX_SIZE) return 0;
    for (int i = 0; i < *n; ++i)
        if (scanf("%d", &a[i]) != 1 || a[i] < -1000000 || a[i] > 1000000) return 0;
    return 1;
}

int linearSearch(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 a[MAX_SIZE], n, key;
    if (!readArray(a, &n) || scanf("%d", &key) != 1) {
        puts("Invalid input."); return 1;
    }
    int index = linearSearch(a, n, key);
    printf("Position: %d\n", index < 0 ? -1 : index + 1);
    return 0;
}

Open in compiler ↗

Code loads into the existing compiler. Enter the sample input there; sign-in and execution rules stay the same.

Compile and run locally

gcc -std=c17 linear-search.c -o lab
./lab

On Windows, run .\lab.exe after compiling with GCC. The interest program requires the math library where applicable.

FOLLOW THE VALUES

Dry run

Step / state	Operation	Result
Array 7,2,9,2; key 2	Check index 0: 7	No match
Check index 1: 2	Match	Return index 1
Display index + 1	First matching position	2

CHECK THE BEHAVIOR

Sample input & output

Each output below was produced by compiling and running this exact program. Input values are entered in the stated order; the examples do not print input prompts.

Sample 1

INPUT

4
7 2 9 2
2

OUTPUT

Position: 2

Sample 2

INPUT

3
1 2 3
8

OUTPUT

Position: -1

Sample 3

INPUT

1
-4
-4

OUTPUT

Position: 1

Common mistakes

Unsorted input is allowed; do not accidentally apply binary-search assumptions.
Return -1 only after all possible elements have been checked.

WHY THIS GROWTH RATE?

Time and space complexity

Time O(n) worst case; O(1) additional search space.

Let n be the number of array elements. The search function checks values one at a time. If the key is missing or only at the end, it performs n comparisons, giving worst-case O(n) search time. If the first element matches, the search itself is O(1).

The complete program must first read all n elements, so its time remains O(n) even when the search finds the first value. The array uses O(n) input storage; the non-recursive search function uses only a loop index, giving O(1) additional search space.

Big-O describes how work grows as the stated input quantity grows; fixed factors and lower-order terms are omitted. The analysis treats fixed-width arithmetic as constant cost and the published limits as practical safety bounds.

PREPARE FOR YOUR LAB VIVA

What you need to solve

Explanation

Algorithm

Flowchart

Complete C program

Dry run

Sample input & output

Sample 1

Sample 2

Sample 3

Common mistakes

Time and space complexity

Related viva questions & answers