Searching Algorithms in C# - Linear Search

In addition to sorting the elements, searching a required piece of data within a collection holds the same significance. Since you already understand how to sort the collections in C#, understanding the searching algorithms would be a piece of cake for you. The searching algorithms provide you with a systematic approach to finding target elements. For beginners in C#, understanding these algorithms can help them create efficient software that performs quick searches based on user needs. In this article, we will cover the linear search algorithm and see its implementation in C#.

Introduction to Searching Algorithms

The searching algorithms provide a structured way of finding an item in a collection. Consider a list of names in a register. What approach will you use if you have to find a particular name? Of course, you go through each entry to see whether the name exists or not. Similarly, given a collection and the targeted value, the searching algorithm first determines if the target exists, and if it does, it finds its location. The efficiency of these algorithms is determined by the number of comparisons they have to make, especially with large datasets.

Linear Search Algorithm (Sequential Search)

As its name suggests, the linear search algorithm looks for the target element linearly by examining each element in the collection and comparing it with the target. This process repeats until either the target value is found or the collection ends without the target being detected. If the element is found, its location is returned. If not, a message is printed on the screen.

To understand this, consider looking up a house number in the street. You go through each house unless you find the target house number. The linear search works the same.

Demonstration

Consider an array of numbers [5, 2, 7, 8, 0, 1]. Let’s suppose we are looking for the number 8 in the array. If we implement the linear search algorithm, it will work as follows:
- Starting with 5, it compares it to 8. Is 5 equals 8? No, it moves forward.
- Compare 2 to 8. Is 2 equals 8? No, it moves forward.
- Compare 7 to 8. Is 7 equals 8? No, it moves forward.
- Compare 8 to 8. Is 8 equals 8? Yes, return its index, i.e. 3.
If we looked for element 9, the algorithm would look for it through the end of the array and would not find the target.

Implementing Linear Search Algorithm in C#

Now that you understand how the linear search algorithm works, it’s time to learn its implementation in C#.

using System;
using System.Collections.Generic;
class Sorting {
    
static int LinearSearch(int[] numbers, int target)
    {
        for(int i = 0; i<numbers.Length; i++)  //Looping through the array
        {
            if(numbers[i] == target)  //Comparing elements with target
            {
                return i;   //returns targets index if found
            }
            
        }
        return 0;  //returns 0 if target is not found
    }
static void Main() {
    int[] nums = {2, 4, 1, 6, 5, 7};
    int location = LinearSearch(nums, 6);  //Calling the linear search function
    if (location != 0)   //if location is not 0
    {
        Console.WriteLine("Item found at " + location);  //prints the location of the target
    }
    else
    {
        Console.WriteLine("Item not found!");
    } 
  }
}

In the above code, I have declared a method called LinearSearch that takes an array and the target element as input. It then compares the target with each element in the array unless the target is found. If no target is found, it returns 0.

Time Complexity Analysis

The linear search algorithm has the following time complexity:

• Best Case: O(1)- This is the case where only 1 comparison is made. The target is the first element of the collection.
• Average Case: O(n)- On average, we expect to find the target somewhere in the middle of the collection. This means roughly half of the array would be examined to find the target.
• Worst Case: O(n) – This is where the maximum comparisons must be made. The target is either the last element of the collection or does not exist at all.

Using Linear Search Algorithm

The linear search algorithm becomes quite useful in situations where:
- You have Smaller Datasets: The linear search algorithms come in handy when you have smaller data sets. Its execution time, compared to other complex algorithms, is almost negligible for the linear search.
- The Data is Unsorted: The linear search algorithm does not require the data to be sorted. It works perfectly with the unsorted data and has no impact on its performance.
- When Searching has to be Done Only Once or a Few Times: When you need to search a dataset only a few times, the linear search algorithm is a better choice since the more advanced algorithms like binary search add the overhead of sorting the data, which can be expensive.

Simply put, the linear search algorithm is a simple but useful searching algorithm. Although it is not suitable for large and frequently searched datasets, it provides a valuable tool for searching unsorted data without any overhead. In the next article, we will explore the Binary Search Algorithm – Another algorithm that uses the Divide and Conquer strategy.