Program 2 : Linear Search

Implement Linear search algorithms and determine the time required to search an element in a list of n numbers. Repeat the experiment for different values of n and plot a graph of the time taken versus n.

Linear Search Logic

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i; 
            // return the index where target is found
    }
    return -1; // target not found
}

int main() {
    int n, target;
	// Getting Array Size
    printf("Enter number of elements: ");
    scanf("%d", &n);
	// Getting Array Elements
    int arr[n];
    printf("Enter %d elements:\n", n);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
	// Getting Target to search
    printf("Enter element to search: ");
    scanf("%d", &target);
	// Searching
    int index = linearSearch(arr, n, target);
	// Result display
	if (index != -1)
        printf("Element found at index: %d\n", index);
    else
        printf("Element not found.\n");

    return 0;
}

With Time Measurement

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

int main() {
    int n, target;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int *arr = (int *)malloc(n * sizeof(int));

    // Fill array with sequential numbers (for simplicity)
    for (int i = 0; i < n; i++)
        arr[i] = i + 1;

    printf("Enter element to search: ");
    scanf("%d", &target);

    clock_t start, end;
    start = clock();

    int index = linearSearch(arr, n, target);

    end = clock();

    double time_taken = (double)(end - start) / CLOCKS_PER_SEC;

    if (index != -1)
        printf("Element found at index: %d\n", index);
    else
        printf("Element not found.\n");

    printf("Time taken: %f seconds\n", time_taken);
    printf("Time taken: %f milliseconds\n", time_taken * 1000);

    free(arr);
    return 0;
}

Code for Plot

import matplotlib.pyplot as plt

sizes = [1000, 5000, 10000, 20000, 50000, 80000, 100000]
times = [0.005, 0.01, 0.03, 0.06, 0.15, 0.25, 0.35]

plt.plot(sizes, times, marker='o', linestyle='-', color='blue')
plt.title('Linear Search Time vs. Input Size (n)')
plt.xlabel('Number of elements (n)')
plt.ylabel('Time (ms)')
plt.grid(True)
plt.tight_layout()
plt.show()