Introduction
In this blog, we will learn about Linear search. Liner search is also known as Sequential Search. As we know searching is one of the most important applications of computing. We will take a simple example of searching an element and will use Liner search to achieve it.
We have two different types of searching techniques,
- Linear Search
- Binary Search
Linear Search
The idea behind linear search is to search a given element in an array. Hence we have to consider below steps
- A given array of size n (let's take size as 5).
- An item to be searched in given array.
- Go through the array till the last element in the array.
- If a match is found, we will return the index position and if not then will return -1.
Pseudocode
function LinearSearch_Algo(array, sizeOfArray, ItemToSearch)
index = 0;
while(index < sizeOfArray)
if(array[index] == ItemToSearch)
return index
index = index+1
return -1
Time Complexity
- Best Case - O(1) Item can be found at first index itself.
- Worst case - O(n) Since in while loop all the elements compared only once.
Let’s Implement it using C#
- Create a simple console application using visual studio.
- Create a class and named it as “LinerSearchAlgo”
- Write a method ExecuteLinearSearch as below code snippet.
public class LinearSearchAlgo {
public int ExecuteLinearSearch(int[] array, int sizeOfArray, int ItemToSearch) {
int index = 0;
while (index < sizeOfArray) {
if (array[index] == ItemToSearch) return index;
index = index + 1;
}
return -1;
}
}
In Program.cs, update Main method as below.
static void Main(string[] args) {
Console.WriteLine("Hello World!");
ExecuteLinearSearch();
}
private static void ExecuteLinearSearch() {
LinearSearchAlgo linearSearchAlgo = new LinearSearchAlgo();
int[] givenAray = {
25,
35,
47,
21,
55,
105,
30,
42
};
int itemToBeSearch = 105;
Console.WriteLine("Searching : " + itemToBeSearch + " in given array...");
int foundIndex = linearSearchAlgo.ExecuteLinearSearch(givenAray, 8, itemToBeSearch);
Console.WriteLine("Item found at inxed : " + foundIndex);
Console.ReadKey();
}
In the above code, we have defined an array and then defined what item we have to search in array. If you run the application, we can clearly see 105 is present at index number 5 in given array.
Summary
In this blog we learned, what is Linear search and how to implement it using C#. In the next blog, we will cover Binary Search with an example.
Thank you!