Linear Search

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.

How Linear Search Works

Start from the beginning: Begin with the first element of the array (index 0).

Compare: Check if the current element matches the target value.

Found or Continue: If a match is found, return the index. If not, move to the next element.

Repeat: Continue this process until either the target is found or all elements have been checked.

Result: Return the index if found, or -1 if the target is not present in the array.

Implementation of Linear Search

//linearsearch.c
#include <stdio.h>
#include <stdlib.h>
int search(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
    if (arr[i] == target) {
        return i; // Return index if found
    }
}
return -1; // Return -1 if not found
}
int main() {
int arr[] = {22, 1, 20, 10, -1, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int idx = search(arr, size, target);
if (idx != -1) {
    printf("The %d is present at index: %d\n", target, idx);
} else {
    printf("Not Present\n");
}
return 0;
}

//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;
}

  #linearsearch.py 
def search(arr, target):
   for i in range(len(arr)):
       if arr[i] == target:
           return i
   return -1

arr = [22, 1, 20, 10, -1, 50]
target = 10
idx = search(arr, target)
if idx != -1:
   print(f"The {target} is present at index: {idx}")
else:
   print("Not Present")

//linearsearch.js
function search(arr, target) {
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === target) {
      return i;
  }
}
return -1;
}

let arr = [22, 1, 20, 10, -1, 50];
let target = 10;
let idx = search(arr, target);
if (idx !== -1) {
console.log(`The ${target} is present at index: ${idx}`);
} else {
console.log("Not Present");
}

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)