Linear search, also sometimes referred as brute-force search or sequential search is one of the simplest search algorithms. It starts with checking if the first element of a list matches the target and continues on for each element of the list till a match is found or the end of the list is reached. For linear search, a data structure like an array or linked list is generally in play. Collections that are only accessible via an iterator are also good candidates for linear search.
The best case is O(1) i.e the target element at first position. The worst case when the element is at the last position is O(n). The average case is also O(n). The code for implementing a linear search is simple.
The best case is O(1) i.e the target element at first position. The worst case when the element is at the last position is O(n). The average case is also O(n). The code for implementing a linear search is simple.
public static bool LinearSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
return true;
}
return false;
}
Why use sequential search?
- If your collection size is relatively small and you would be performing this search relatively a few times, then this might an option.
- Another case is when you need to have constant insertion performance (like using a linked list) and the search frequency is less.
- In addition, linear search places very few restrictions on the complex data types. All that is needed is a match function of sorts.
If the elements you would be searching in a list are NOT uniformly distributed, then you could do certain optimizations that can help you improve the efficiency of your search algorithms. For such improvements to be effective, you do need to know the characteristics of the data being searched, the frequency and also the fact that the underlying collection needs to be modifiable.
- Most Recently Used pattern: If the likelihood of the current element being searched again is high, then move if from it's current location (say position i) to the front of the collection (say position 0). This does require moving elements from A[0, i-1] to A[1, i] to accommodate the new element at A[0].
- The disadvantage of the above pattern is that it requires a lot of movement. One quick strategy is to move an element up on success by simply swapping the target element from position x with the first element at position 0. This eventually results in a similar pattern as the frequently searched elements bubble up to the top of the list.
- On the other end of the spectrum, if an element is unlikely to be search again, then moving it to the end on find improves the chances of the other elements being searched.