×

Courses

Chapters

>
<

Data Structure

Linear Search | CrackEase

Linear Search

Linear search illustration

Linear Search

Searching means finding whether a given element exists in a collection and — if it exists — determining its position. In data structures there are many searching algorithms; two common simple ones are:

  1. Linear search (also called sequential search)
  2. Binary search (requires sorted data)

Linear Search Algorithm
Linear search algorithm flowchart
Steps to Perform Linear Search

Step 1 — Take array input and determine the number of elements. Call this arr with length n.

Step 2 — Take the input for the item to be searched in the array. Call this item.

Step 3 — Linearly traverse the array using a loop from index 0 to n-1.

Step 4 — For each array element check if arr[i] == item:

  • If the condition is met, print the value and its position and return from the function.
  • If the loop finishes without a match, print "Not Found".

Code
  
#include<stdio.h>

void LinearSearch(int arr[], int len, int item)
{
    for(int i = 0; i < len; i++)
    {
        if(arr[i] == item)
        {
            printf("%d Found at index %d", item, i);
            return;
        }
    }
    printf("Not Found");
}

int main() 
{
    int arr[] = {10, 20, 30, 40, 50};

    // calculating length of array 
    int len = sizeof(arr) / sizeof(arr[0]);

    // item to be searched
    int item = 40;
    LinearSearch(arr, len, item);

    return 0;
}
  

  
#include<iostream>
using namespace std;

void LinearSearch(int arr[], int len, int item) {
    for(int i = 0; i < len; i++) {
        if(arr[i] == item) {
            cout << item << " Found at index : " << i;
            return;
        }
    }
    cout << "Not found";
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};

    // calculating length of array 
    int len = sizeof(arr) / sizeof(arr[0]);

    // item to be searched
    int item = 40;
    LinearSearch(arr, len, item);

    return 0;
}
// extra space: O(1) (in-place, no auxiliary array)
// time complexity : O(n)
  

  
class Main {

    private static void LinearSearch(int[] arr, int item) {

        for(int i = 0; i < arr.length; i++){
            if(arr[i] == item)
            {
                System.out.println(item + " Found at index : " + i);
                return;
            }
        }
        System.out.println("Not found");

    }

    public static void main(String args[]) {
        int[] arr = {10, 20, 30, 40, 50};

        int item = 40;
        LinearSearch(arr, item);
    }
}
// extra space: O(1)
// time complexity: O(n)
	

	
40 Found at index 3
More about Linear Search
Pros

  • Very easy to understand and implement.
  • Works on unsorted data and small arrays efficiently in practice.

Cons

  • Time complexity is linear: O(n), so it's slow for large datasets compared to more advanced searches (e.g., binary search on sorted data).

Time Complexity for Linear Search
BestAverageWorstSpace ComplexityAverage Comparisons
O(1)O(n)O(n)O(1)(n+1)/2
Footer Content | CrackEase
→
←