Implementing Linear Search

Welcome to Module 8! In our last lesson, we developed a formal method for analyzing algorithms by counting their primitive operations to derive a cost function. This gave us a rigorous way to determine Big-O complexity. Now, it's time to apply this powerful tool to our first proper searching algorithm.

This lesson introduces linear search, a fundamental and intuitive method for finding an element within an array. You will learn its simple logic, implement it in C, and, most importantly, use the analysis techniques from the previous module to determine its time complexity. This marks our first step in building a toolbox of standard algorithms.

1. The Concept of Linear Search

Linear search, also known as sequential search, is the most straightforward way to look for a value in a collection of items. The strategy is simple: start at the very first element, check if it's the one you're looking for, and if not, move to the next one. You repeat this process sequentially until you either find the target or you've checked every single element.

To see this process in motion, let's watch a short video that explains the working principle.

As you saw, the logic is very direct. This simplicity is one of its main strengths, especially when dealing with data that isn't sorted in any particular order.

2. Implementing Linear Search in C

Now, let's translate this logic into C code. The core of the linear search algorithm is a for loop that iterates through the array from the first element (index 0) to the last. Inside the loop, an if statement checks if the current element matches our target value.

A key design choice is how to communicate the result. A common and effective C practice is to have the search function return the index of the element if found, and a special value, typically -1, if the element is not in the array. Since array indices are always non-negative (0 or greater), -1 serves as a clear signal that the search was unsuccessful.

The following video walks through writing the C code for a linear search function that implements this return -1 strategy.

The video highlights an important efficiency point: using return inside the loop stops the search immediately upon finding a match. This avoids unnecessary checks of the remaining elements. This is a more elegant approach than using a break statement followed by another check outside the loop.

3. Analyzing the Time Complexity

With the implementation clear, we can now analyze its performance. This is a direct application of what we learned in the last lesson about counting operations. The key "work" inside the loop is the comparison (arr[i] == target). How many times does this comparison happen? It depends. Let's analyze the best, worst, and average cases.

The next video segment provides an excellent analysis of these scenarios.

Let's summarize the analysis. If the array has $n$ elements:

• Best Case: The target is at index 0. We do just one comparison. The complexity is O(1), or constant time.
• Worst Case: The target is at index $n-1$, or it's not in the array. We must perform $n$ comparisons. The cost function is linear (e.g., $T(n)=c\cdot n+d$), so the complexity is O(n).
• Average Case: Assuming the element has an equal chance of being at any position, we will, on average, search through about half the array, making $n/2$ comparisons. Since we drop constant factors in Big-O notation, the average-case complexity is also O(n).

In algorithm analysis, we are typically most concerned with the worst-case complexity, as it gives us a guaranteed upper bound on performance. Therefore, we state that the time complexity of linear search is O(n).

For a supplementary explanation, you can review the following article which consolidates these ideas.

4. Practice: Your First Search Program

Now it's time to put everything together. Below is a complete C program that uses the linearSearch function. Your task is to compile and run this code to solidify your understanding.

#include <stdio.h>

// Function to perform linear search on an array
// arr: the array to search in
// size: the number of elements in the array
// target: the value to search for
// Returns the index of the target if found, otherwise returns -1
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Target found, return its index
        }
    }
    return -1; // Target not found after checking all elements
}

int main() {
    int numbers[] = {22, 35, 12, 5, 48, 62, 17};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    int target1 = 48;
    int target2 = 99; // A value not in the array

    // --- Test Case 1: Element is in the array ---
    int result1 = linearSearch(numbers, size, target1);

    if (result1 != -1) {
        printf("Target %d found at index: %d\n", target1, result1);
    } else {
        printf("Target %d was not found in the array.\n", target1);
    }

    // --- Test Case 2: Element is NOT in the array ---
    int result2 = linearSearch(numbers, size, target2);

    if (result2 != -1) {
        printf("Target %d found at index: %d\n", target2, result2);
    } else {
        printf("Target %d was not found in the array.\n", target2);
    }

    return 0;
}

Your Task:

1. Copy this code into your development environment.
2. Compile and run it. Verify that the output is correct: 48 should be found at index 4, and 99 should not be found.
3. Modify the main function to search for other values. Try searching for 22 (the best case) and 17 (the worst case where the element is present).
4. Challenge Question: The linearSearch function stops and returns the index of the first occurrence of a target. How would you modify the program if you wanted to find all indices of a target value that might appear multiple times in the array? (You don't need to write the full code, just think through the logical changes you would need to make.)

Conclusion

Congratulations on implementing and analyzing your first searching algorithm! While simple, linear search is an essential building block and a perfect case study for applying complexity analysis.

Key Takeaways:

• Linear search sequentially inspects each element in a list until a match is found or the list ends.
• It is simple to implement with a for loop and an if condition.
• Returning -1 is a standard C convention to indicate that an element was not found.
• The time complexity of linear search is O(n), as in the worst case, it must scan the entire array.
• Its space complexity is O(1) because it requires no extra storage that scales with the input size.

Preview of the Next Lesson:
Linear search works on any array, sorted or not. But what if we know the array is sorted? Can we do better than checking every single element? The answer is a resounding yes! In the next lesson, we will explore binary search, a much more efficient algorithm that leverages a sorted array to find elements with an impressive O(log n) time complexity.