Linear Search is the simplest search algorithm. It checks every element in sequence until it finds the target or exhausts the array. It requires no preprocessing and works on unsorted data, making it universally applicable despite its O(n) time complexity.
int linearSearch(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++)
if (arr[i] == target) return i;
return -1;
}Linear Search starts at index 0 and checks each element in turn. If the current element matches the target it returns the index. If the end of the array is reached without a match it returns -1.
Use Linear Search on unsorted arrays or when the array is very small. For sorted data, Binary Search is far more efficient. Linear Search is also used as a fallback when preprocessing cost is not justified.
Best case O(1) when the target is the first element. Average and worst case are O(n). Space is O(1) as no auxiliary storage is needed.
Linear Search is preferred over Binary Search when:
What is the worst-case time complexity of Linear Search?
Linear Search on an unsorted array finds: