Linear Search: Implementation and O(n) Complexity

1. What is Linear Search?

Imagine you're looking for a specific book on a single, messy shelf. The most direct approach is to start at one end and check each book, one by one, until you find the one you're looking for. This is the exact idea behind linear search.

In programming terms, linear search is an algorithm that finds a target value within a list (or array) by sequentially checking each element from the beginning until a match is found or the entire list has been checked.

Let's look at a visual representation of this process.

To solidify this concept, let's walk through a step-by-step example.

2. Implementing Linear Search in Python

Now that you understand the logic, let's translate it into Python code. Our function will need two pieces of information:

1. The list to search through (arr).
2. The value we are looking for (targetVal).

The function should return the index of the target if it's found. If the target is not in the list, it's a common convention to return -1 to signal that the search was unsuccessful.

The W3Schools page you just read has a great Python implementation.

Here is the code from the resource for your reference. Let's break it down:

def linearSearch(arr, targetVal):



    # Iterate through the list using the index 'i'
    for i in range(len(arr)):



        # Check if the element at the current index matches the target
        if arr[i] == targetVal:



            # If it matches, stop searching and return the index
            return i
    



    # This line is only reached if the loop finishes without finding the target
    return -1




# --- Let's test it! ---
my_list = [12, 8, 9, 11, 5, 17]




# Case 1: Target is in the middle
target1 = 9
result1 = linearSearch(my_list, target1)
print(f"Searching for {target1}: Found at index {result1}")




# Case 2: Target is not in the list
target2 = 100
result2 = linearSearch(my_list, target2)
if result2 != -1:
    print(f"Searching for {target2}: Found at index {result2}")
else:
    print(f"Searching for {target2}: Not found in the list.")

Your Turn: Practice with the Code

1. Copy the linearSearch function and the test cases into a Python file.
2. Run the code to confirm the output.
3. Add a few more test cases:
   • Search for the value at the very beginning of the list (12).
   • Search for the value at the very end of the list (17).
4. Predict the output before you run the code for your new test cases. This will help confirm your understanding of the algorithm's flow.

3. Analyzing the Time Complexity

In Module 4, you learned that we analyze algorithm efficiency by counting the number of basic operations relative to the input size, n. For linear search, the most important operation is the comparison: arr[i] == targetVal.

How many comparisons will we make? It depends on where the target is.

Let's read a short article that explains these cases in detail.

Here's a summary of the key points from the reading:

• Best Case: O(1)
  This happens if the element we're looking for is the very first item in the list. The algorithm performs just one comparison and returns immediately, regardless of how long the list is. This is constant time.

• Worst Case: O(n)
  This occurs if the element is at the very end of the list, or if it's not in the list at all. In this scenario, the algorithm must perform n comparisons (where n is the number of elements in the list).

• Average Case: O(n)
  On average, we can expect the element to be somewhere in the middle of the list. This means we'll perform roughly n/2 comparisons. However, in Big O notation, we ignore constant factors (like 1/2), so the average case is still considered O(n).

Because the performance depends directly on the number of elements, n, we say linear search has a linear time complexity.

Visualizing the Step Count

To make this more concrete, let's watch a short video clip. The presenter is using Java, but the concept he demonstrates is universal. He adds a steps counter inside his loop to physically count how many times the loop runs.

This demonstration clearly shows that for a list of n items, finding the last item takes approximately n steps, which is the core idea behind O(n) complexity.

Conclusion

Great work today! You've successfully implemented your first searching algorithm and analyzed its performance—a critical skill for any programmer.

Key Takeaways:

• Linear search is a straightforward algorithm that inspects each element of a list one by one until a target is found.
• It is implemented in Python using a for loop to iterate through the list and an if statement to check for a match.
• The time complexity of linear search is:
  • Best Case: O(1) (target is the first element).
  • Worst/Average Case: O(n) (runtime grows linearly with the list size).
• Linear search is simple and effective for small or unsorted lists.

Preview of the Next Lesson:
Linear search is intuitive, but its O(n) performance can be very slow for large datasets (e.g., millions of items). What if our list was sorted? Could we use that information to search faster? In the next lesson, we will explore binary search, a much more efficient algorithm that uses a "divide and conquer" strategy to achieve an impressive O(log n) time complexity on sorted data.