Searching Algorithms: Linear Search in C

What You’ll Learn 📚

• Understanding what a linear search is and when to use it
• Key terminology and concepts
• How to implement a linear search in C with examples
• Common questions and troubleshooting tips

Introduction to Linear Search

Linear search is one of the simplest searching algorithms. It’s like looking for a book in a stack by checking each one until you find the right one. Easy, right? 😊 Linear search is a great starting point for understanding more complex algorithms later on.

Key Terminology

• Algorithm: A step-by-step procedure to solve a problem.
• Search Key: The item you’re looking for in a collection.
• Array: A collection of items stored at contiguous memory locations.

Simple Example: Linear Search in C

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            return i; // Return the index where the key is found
        }
    }
    return -1; // Return -1 if the key is not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int key = 30;
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, size, key);
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }
    return 0;
}

Progressively Complex Examples

Example 2: Linear Search with User Input

#include <stdio.h>

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

int main() {
    int arr[100], size, key;
    printf("Enter the number of elements: ");
    scanf("%d", &size);
    printf("Enter %d elements: ", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    printf("Enter the element to search: ");
    scanf("%d", &key);
    int result = linearSearch(arr, size, key);
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }
    return 0;
}

Example 3: Linear Search with Strings

#include <stdio.h>
#include <string.h>

int linearSearch(char arr[][20], int size, char key[]) {
    for (int i = 0; i < size; i++) {
        if (strcmp(arr[i], key) == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    char arr[5][20] = {"apple", "banana", "cherry", "date", "fig"};
    char key[20];
    printf("Enter the fruit to search: ");
    scanf("%s", key);
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, size, key);
    if (result != -1) {
        printf("Fruit found at index: %d\n", result);
    } else {
        printf("Fruit not found in the array.\n");
    }
    return 0;
}

Common Questions and Answers

1. What is linear search?

   Linear search is a simple algorithm that checks each element in a list until it finds the target element or reaches the end of the list.

2. When should I use a linear search?

   Use linear search when the list is small or unsorted, as it's straightforward but not the most efficient for large datasets.

3. What is the time complexity of linear search?

   The time complexity is O(n), where n is the number of elements in the array. This means the time taken grows linearly with the number of elements.

4. Why does linear search return -1?

   Returning -1 indicates that the search key was not found in the array. It's a common convention to signify failure in searches.

5. Can linear search be used on sorted arrays?

   Yes, but there are more efficient algorithms like binary search for sorted arrays.

Troubleshooting Common Issues

Ensure your array indices are within bounds. Accessing out-of-bounds indices can lead to undefined behavior.

If your program isn't finding an element, double-check your loop conditions and ensure the key is correctly passed to the function.

Practice Exercises

• Modify the user input example to handle floating-point numbers.
• Implement a linear search for a 2D array.
• Write a program to count the occurrences of a search key in an array.

Keep practicing, and remember, every expert was once a beginner. You're doing great! 🌟