AlgoViz
HomeArrays & Hashing

Linear Search

Easy

Scan until you find it

Problem

Given an array of integers nums and an integer target, find the smallest index (0 based indexing) where the target appears in the array. If the target is not found in the array, return -1

In simple words

Check each box left to right until you spot the number you want.

The idea

Walk from the front and return the first index whose value matches. It makes no assumptions at all about the data, which is why it is the fallback when the array is unsorted and you cannot afford to sort it.

The trick

  • Return the first match to get the smallest index.
  • O(n), but O(log n) is available the moment the array is sorted.
i
2
3
4
5
3
0
1
2
3
4
target5

Step 1 of 4. nums[0] = 2 ≠ 5. Values: 2, 3, 4, 5, 3. Pointers: i at index 0. target 5.

1/4
Optimal
timeO(n)spaceO(1)
1for i in 0..n-1:2  if nums[i] == target: return i3return -1

Input

array
[2, 3, 4, 5, 3]
target
5

Memory

i
= 0 [2]
target
5

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [6, 7, 8, 9], target = 8
Output:
2
Explanation:
8 sits at index 2 (counting from 0).

Example 2

Input:
nums = [1, 2, 3], target = 5
Output:
-1
Explanation:
5 is not in the list, so return -1.

Example 3

Input:
nums = [4, 4, 4], target = 4
Output:
0
Explanation:
The first 4 is found at index 0.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • -10^4 <= target <= 10^4

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.