Linear Search in Array

Given an array of integers and a target value called key, your task is to search for the key in the array using linear search.

• In linear search, we check each element one by one from left to right.
• If the key is found, return the index of the first occurrence of the key.
• If the key is not present in the array, return -1.

This is the simplest and most intuitive way to search for a value in an array.

Understanding the Problem: Linear Search

We are given an array and a target value called the key. Our task is to search for this key in the array and return the index where it is found. If it is not found, we return -1.

This is a classic searching problem and we will solve it using the Linear Search method — which is the simplest way to go through elements one by one until we find a match.

Step-by-Step Approach with Example

Let’s take an example to understand it clearly:

Array: [3, 7, 1, 9, 5]
Key: 9

Step 1: Start from the beginning

We begin checking from the first element (index 0):

• Check index 0 → 3 ≠ 9
• Check index 1 → 7 ≠ 9
• Check index 2 → 1 ≠ 9
• Check index 3 → 9 = 9 → Found! Return index 3

Intuitive Explanation

Think of it like flipping through pages of a notebook looking for a word. You start from the first page and go one by one until you find what you’re looking for. That’s what linear search does — no skipping or assumptions.

Handling Edge Cases

• Key Not Present: What if the key doesn’t exist? Example: [3, 7, 1, 9, 5], key = 4 → We check all elements and return -1 since 4 is not found.
• Empty Array: No elements to search? Just return -1 instantly.
• Single Element Array: For example, [5] and key = 5 → we return index 0. If key = 3 → return -1.
• Multiple Occurrences: In [1, 5, 3, 5, 9] with key = 5 → return index 1 because we return the first match we find.

Why Linear Search Works Well in Some Situations

• It’s simple and requires no sorting or preparation.
• Works for both sorted and unsorted arrays.
• Perfect for small datasets or quick one-time checks.

Final Thought

Linear search may not be the most efficient for large arrays, but it’s the most intuitive and beginner-friendly. If you need to search in an array without any advanced requirements, linear search is a great place to start!

1. Given an array arr and a target key.
2. Iterate through the array from index 0 to n-1.
3. For each element, check if arr[i] == key.
4. If a match is found, return the index i.
5. If no match is found after the loop ends, return -1.

Worked example

We are performing a linear search for the value 40 in the array.

Check index 0

Compare arr[0] = 10 with key = 40.

No match. Continue to next index.

Check index 1

Compare arr[1] = 20 with key = 40.

No match. Continue to next index.

Check index 2

Compare arr[2] = 30 with key = 40.

No match. Continue to next index.

Check index 3

Compare arr[3] = 40 with key = 40.

Match found! Element 40 is equal to key 40. Return index 3.

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) return i;
    }
    return -1;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int key = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = linearSearch(arr, n, key);
    printf("Element found at index: %d\n", index);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int linearSearch(const vector<int>& arr, int key) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == key) return i;
    }
    return -1;
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50};
    int key = 30;
    cout << "Element found at index: " << linearSearch(arr, key) << endl;
    return 0;
}

def linear_search(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

# Sample Input
arr = [10, 20, 30, 40, 50]
key = 30
print("Element found at index:", linear_search(arr, key))

public class LinearSearch {
    public static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int key = 30;
        System.out.println("Element found at index: " + linearSearch(arr, key));
    }
}

function linearSearch(arr, key) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === key) {
            return i;
        }
    }
    return -1;
}

// Sample Input
const arr = [10, 20, 30, 40, 50];
const key = 30;
console.log('Element found at index:', linearSearch(arr, key));

package main

import (
    "fmt"
)

func linearSearch(arr []int, key int) int {
    for i, val := range arr {
        if val == key {
            return i
        }
    }
    return -1
}

func main() {
    arr := []int{10, 20, 30, 40, 50}
    key := 30
    fmt.Println("Element found at index:", linearSearch(arr, key))
}

fn linear_search(arr: &[i32], key: i32) -> i32 {
    for (i, &val) in arr.iter().enumerate() {
        if val == key {
            return i as i32;
        }
    }
    -1
}

fn main() {
    let arr = [10, 20, 30, 40, 50];
    let key = 30;
    println!("Element found at index: {}", linear_search(&arr, key));
}

fun linearSearch(arr: IntArray, key: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == key) return i
    }
    return -1
}

fun main() {
    val arr = intArrayOf(10, 20, 30, 40, 50)
    val key = 30
    println("Element found at index: ${linearSearch(arr, key)}")
}

func linearSearch(arr: [Int], key: Int) -> Int {
    for (i, val) in arr.enumerated() {
        if val == key {
            return i
        }
    }
    return -1
}

let arr = [10, 20, 30, 40, 50]
let key = 30
print("Element found at index: \(linearSearch(arr: arr, key: key))")

function linearSearch(arr: number[], key: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === key) {
            return i;
        }
    }
    return -1;
}

const arr: number[] = [10, 20, 30, 40, 50];
const key: number = 30;
console.log("Element found at index:", linearSearch(arr, key));

Time complexity

Space complexity

O(1)

The algorithm uses a constant amount of extra space—just a loop variable and the target value—regardless of the array size.