Linear Search in Array - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpaceDetailed Ex

Visualization Player

Problem Statement❯

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.

Examples❯

Input Array Key Output Description
[10, 20, 30, 40, 50] 30 2 30 is present at index 2Visualization
[5, 8, 12, 8, 20] 8 1 First occurrence of 8 is at index 1Visualization
[1, 2, 3, 4, 5] 6 -1 6 is not in the arrayVisualization
[] 5 -1 Array is empty, so nothing to searchVisualization
[42] 42 0 Single element matches the keyVisualization
[42] 99 -1 Single element does not matchVisualization
[1, 1, 1, 1] 1 0 All elements match, but return the first indexVisualization

Solution❯

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!

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target element is found at the very first index of the array.
Average CaseO(n)On average, the search will check half of the array before finding the target or confirming it doesn't exist.
Worst CaseO(n)In the worst case, the algorithm will check every element in the array, either finding the target at the end or not finding it at all.

Space Complexity❯

O(1)

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

Detailed Step by Step Example❯

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

{ "array": [10,20,30,40,50], "showIndices": true }
{ "array": ["key:", 40], "emptyIndices": [0], "highlightIndicesGreen": [1] }

Check index 0

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

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [0], "labels": {"0":"i"} }

No match. Continue to next index.

Check index 1

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

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [1], "labels": {"1":"i"} }

No match. Continue to next index.

Check index 2

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

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndices": [2], "labels": {"2":"i"} }

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.

{ "array": [10,20,30,40,50], "showIndices": true, "highlightIndicesGreen": [3], "labels": {"3":"i"} }

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...