Skip to main content
CodePeet

Linear Search

Try it yourself
EasyProblem

Description

Given an array arr and a value target, return the index of the first element equal to target. If no element equals it, return -1.

Examples

Example 1

Input: arr = [4, 2, 7, 2], target = 2

Output: 1

Explanation: 2 is at indexes 1 and 3; the first is 1.

Example 2

Input: arr = [4, 2, 7], target = 5

Output: -1

Explanation: 5 isn't in the array.

Example 3

Input: arr = [9], target = 9

Output: 0

Explanation: The only element is the target, at index 0.

Example 4

Input: arr = [1, 2, 3], target = 3

Output: 2

Explanation: The target is the last element, at index 2.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • -10^9 ≤ arr[i], target ≤ 10^9

Editorial

Approach - Check Each Element in Turn

Intuition

The array isn't sorted, so an element anywhere could be the target, and nothing short of looking tells you where. Look at each one from the left. The first match is the answer, so return its index the moment you find it; if the loop ends without one, the target isn't there, and -1, which no index can be, says so.

Step-by-Step Explanation

Let's trace Example 1, arr = [4, 2, 7, 2], target = 2:

  1. arr[0] = 4: not 2.
  2. arr[1] = 2: it's the target.
  3. Return 1 at once: any later match comes after this one.

Check Each Element — Each element is compared with the target, left to right, until the first match.

Algorithm

  1. For each index i from 0 to the end: if arr[i] == target, return i.
  2. Return -1.

Code

class Solution {
public:
    int linearSearch(vector<int>& arr, int target) {
        for (int i = 0; i < (int) arr.size(); i++) {
            if (arr[i] == target) return i;     // the first match: stop here
        }
        return -1;
    }
};

from typing import List

class Solution:
    def linearSearch(self, arr: List[int], target: int) -> int:
        for i in range(len(arr)):
            if arr[i] == target:
                return i                    # the first match: stop here
        return -1

class Solution {
    public int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;     // the first match: stop here
        }
        return -1;
    }
}

var linearSearch = function(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;    // the first match: stop here
    }
    return -1;
};

Complexity Analysis

Time Complexity: O(n)

Each element is compared at most once; a missing target means all n.

Space Complexity: O(1)

Only the index.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Stopping one element early. range(len(arr) - 1)

On arr = [1, 2, 3], target = 3 it returns -1; the answer is 2. range(len(arr) - 1) stops before the last index, so a target sitting only at the end is never looked at. range(len(arr)) already ends at the last index.

Keeping going after a match. found = i

On arr = [4, 2, 7, 2], target = 2 it returns 3; the answer is 1. Remembering every match and returning at the end gives the last occurrence, not the first. Return as soon as one is found.

Returning 0 when it isn't there. return 0

On arr = [4, 2, 7], target = 5 it returns 0; the answer is -1. 0 is a real index: it means the target is the first element. "Not found" needs a value no index can have, which is why it's -1.

Where This Pattern Is Taught

This problem practises reading an array by index, from the first element to the last. It's taught in Introduction to Arrays.