Linear Search

Sequential Search to Find Target

Introduction

Linear Search is a simple search algorithm that checks each element one by one until the target element is found or the end is reached. It works on both sorted and unsorted data but is less efficient for large datasets compared to more advanced algorithms like binary search. Linear search has a time complexity of O(n), where n is the number of elements.

1

Start at the first element.

2

Compare the current element with the target value.

  • If they match, return the current index (or true).
  • If they don’t match, move to the next element.
3

Repeat

  • Repeat the process until the target is found or the total search is finished.
//linearsearch.cpp
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++)
    if (arr[i] == target)
        return i;
return -1;
}
int main() {
vector<int> arr = {22,1,20,10,-1,50};
int target = 10;
int idx = search(arr, target);
if (idx != -1)
    cout << "The "<<target<<" is present at index: "<<idx;
else
   cout << "Not Present";
return 0;
}

Time Complexity

  • Best case: O(1), When the target element is found at the first position in the array.
  • Average case: O(n),When the target is found somewhere in the middle of the array .
  • Worst case: O(n), wWhen the target element is at the end of the array or not present at all. Here, the algorithm must check each element in the array to find the target.

Space Complexity

Space Complexity:O(1)