Linear Search
p
M
O
A
�
R
P
S
using Utilities.Exceptions;
namespace Algorithms.Search;
/// <summary>
/// Class that implements linear search algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class LinearSearcher<T>
{
/// <summary>
/// Finds first item in array that satisfies specified term
/// Time complexity: O(n)
/// Space complexity: O(1).
/// </summary>
/// <param name="data">Array to search in.</param>
/// <param name="term">Term to check against.</param>
/// <returns>First item that satisfies term.</returns>
public T Find(T[] data, Func<T, bool> term)
{
for (var i = 0; i < data.Length; i++)
{
if (term(data[i]))
{
return data[i];
}
}
throw new ItemNotFoundException();
}
/// <summary>
/// Finds index of first item in array that satisfies specified term
/// Time complexity: O(n)
/// Space complexity: O(1).
/// </summary>
/// <param name="data">Array to search in.</param>
/// <param name="term">Term to check against.</param>
/// <returns>Index of first item that satisfies term or -1 if none found.</returns>
public int FindIndex(T[] data, Func<T, bool> term)
{
for (var i = 0; i < data.Length; i++)
{
if (term(data[i]))
{
return i;
}
}
return -1;
}
}
About this Algorithm
Problem Statement
Given an array of n elements, write a function to search for the index of a given element (target)
Approach
- Start iterating with the first element in the array.
- Compare it with the target element
- If it is equal to the target element then return the index
- Else continue iterating
- Return -1 if target element is not found in the array
Time Complexity
O(n) Worse Case
O(1) Best Case (If first element of array is the target element)
Space Complexity
O(1)
Example
arr = [1, 3, 9, 5, 0, 2]
target = 5
Linear Search should return index 3 as 5 is on index 3
target = 6
Linear Search should return -1 as 6 is not present in the array
Video Explanation
A CS50 video explaining the Linear Search Algorithm
