Algorithm

Array Traversal (Linear Search)

Arrays & Strings Pattern

Array Traversal (Linear Search)

Given an array of integers nums and a target value, return the index of the first occurrence of target in nums. If target does not appear in the array, return -1. The array is not sorted.

CONSTRAINTS
  • 0 <= nums.length <= 10⁵
  • -10⁹ <= nums[i] <= 10⁹
  • -10⁹ <= target <= 10⁹
EXAMPLE 1
Input: nums = [12, 45, 7, 23, 56], target = 7
Output: 2
We check 12 (index 0), then 45 (index 1), then find 7 at index 2. Positions count from 0 — which is why the answer is 2, not 3.
EXAMPLE 2
Input: nums = [5, 3, 5], target = 5
Output: 0
5 appears at index 0 and index 2. We return 0, the first occurrence.
EXAMPLE 3
Input: nums = [1, 2, 3], target = 4
Output: -1
Every element is checked and 4 never appears. -1 means 'not found' — it can never be mistaken for a real position, since positions start at 0.
EXAMPLE 4
Input: nums = [], target = 3
Output: -1
An empty array has nothing to check, so the target is certainly not there.
Is the array sorted, or in any particular order?
No — assume the values are in no particular order. This is always worth asking in a search problem: ordered data unlocks much faster techniques, and the interviewer's answer decides which approaches are even possible.
Should I return the value, its index, or just true/false?
Return the index of the first occurrence — and -1 when the target is absent.
If the target appears multiple times, which index should I return?
The index of the first occurrence, i.e. the smallest such index.
How should I handle an empty array?
An empty array can never contain the target, so return -1.

Searching for a target in an unordered list is about systematic verification. Since there is no sorted order to exploit, we must check every element one-by-one.

Linear Scan (O(N))

We start at the beginning of the array and compare each value to our target. If we find a match, we return the index. If we reach the end without a match, we can say for certain the target isn't there. This is the only way to search unsorted data.

python
for i in range(len(nums)):
    if nums[i] == target:
        return i
return -1
Worked Example:[12, 45, 7, 23], target 7
0
12
i
1
45
2
7
3
23
We check the element at index 0, which is 12. Since it does not match our target value of 7, we move to the next index.
0
12
1
45
i
2
7
3
23
We check the element at index 1, which is 45. Since it does not match our target value of 7, we continue our search.
0
12
1
45
2
7
i
3
23
We check the element at index 2, which is 7. This matches our target value, so we return index 2 and terminate the search.
Interactive Strategy Visualization

Linear Search

Target: 23
12
0
45
1
7
2
23
3
56
4
18
5
91
6
We need to find a needle in a haystack.
MINDSET

Scanning every element one-by-one until the target is found or we run out of elements.

PERFORMANCE

In the worst case, we must visit all N items. Complexity: O(N).

O(N) Linear Scan — Optimal for Unsorted Data