Linear Search in Array using Loop

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace Detailed Exmpl

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

Visualization Player

Solution❯

Linear search is one of the most basic and widely used methods for finding a value in an array. The idea is simple: go through each element from the beginning and compare it with the target value (key).

How It Works in Practice

Start from the first element of the array and compare it with the key:

  • If the current element equals the key, we immediately return that index.
  • If not, move to the next element and repeat.

If we reach the end of the array without finding the key, we return -1 to indicate that the key is not present.

Understanding Different Scenarios

  • Normal Case: If the key exists somewhere in the array, linear search will find it. The time it takes depends on where the key is located—beginning (fast), middle (moderate), or end (slow).
  • Multiple Occurrences: If the key appears multiple times, the function will return the index of the first occurrence.
  • Key Not Present: If the key is not in the array at all, we go through the entire array and return -1 at the end.
  • Empty Array: If the array has no elements, there is nothing to check. So, we directly return -1.
  • Single Element Array: If the array has only one element, the answer will either be index 0 if it matches the key, or -1 if it doesn’t.

Why Use Linear Search?

While not the fastest for large arrays, linear search works well for small arrays or when the data is unsorted. It’s also very easy to implement and understand.

Overall, linear search is the go-to method when you need a quick, simple way to check if a value exists in an array without any advanced setup or sorting.

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

Python
JavaScript
Java
C++
C
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))

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"} }