ToolMight LogoToolMight
EasyArrays & HashingPattern: Sequential ScanPattern: Brute Force

Linear Search

The foundational search algorithm for unsorted collections. Scans elements one by one until a match is found or the list is exhausted.

Problem Statement

Given an array of integers nums and an integer target, write a function to search for target in nums.

If target exists in the array, return its 0-based index. If target is not present, return -1.

Linear Search is the baseline search algorithm for unsorted data, evaluating each item sequentially until a match is detected or the collection is exhausted.

Examples & Constraints

Example 1
Input: nums = [4, 2, 7, 1, 9, 3], target = 7
Output: 2
Explanation: 7 is located at index 2.
Example 2
Input: nums = [10, 20, 30, 40, 50], target = 25
Output: -1
Explanation: 25 does not exist in nums, so -1 is returned.
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i], target <= 10^4
  • Array elements may be in arbitrary, unsorted order.

Select Approach (2 Solutions)

Sequential Scan (Single Pass)

Optimal Approach
Time:O(n)
Space:O(1)

Iterate through the array from left to right, comparing each element with the target value until found.

Time ComplexityO(n)

In the worst case (target at the end or not present), the algorithm checks all N elements exactly once.

Space ComplexityO(1)

Operates in-place using only a single loop counter variable with zero additional memory allocation.

Underlying algorithmic logic

The Core Mental Model: The Unsorted Room

Imagine searching for your lost keys in an unsorted room: without an indexing system or sorted shelves, your only guaranteed strategy is to check each spot sequentially until the item turns up or you have checked every single corner.

Step-by-Step Execution Logic

The algorithm executes an exhaustive single-pass loop with immediate early termination:

  1. Pointer Initialization: Start an index counter i = 0 representing the first element of the collection.
  1. Sequential Equality Check: At each step, inspect the candidate element at nums[i] and compare it to target:
  • Match Found (`nums[i] === target`): The target is located. Immediately return `i` (early return). There is no need to examine any remaining elements.
  • Mismatch (`nums[i] !== target`): Advance the index pointer (i++) to move forward to the next element.
  1. Exhaustion Fallback (Missing Element): If the loop scans through index n - 1 and terminates without finding a match, you have proven that target does not exist anywhere in nums. Return -1.

Critical Invariants & Edge Cases

  • Empty Array (`nums.length == 0`): The loop boundary condition i < nums.length immediately evaluates to false, gracefully returning -1 without any index-out-of-bounds errors.
  • First Element Match (Best Case `O(1)`): When target is located at nums[0], the algorithm returns on its very first comparison.
  • Last Element or Missing (Worst Case `O(n)`): The algorithm inspects all N elements before returning.
  • Duplicate Elements: Standard left-to-right scan is deterministic—it always returns the first occurrence (lowest index) of the matching target.

Why Senior Engineers Still Care About Linear Search

A common beginner misconception is: "Linear search is `O(n)`, so it's obsolete."
In real-world systems engineering, Linear Search is frequently chosen over Binary Search and Hash Maps for three critical reasons:

  1. CPU Cache Locality & Hardware Prefetching: Contiguous array memory allows the CPU to load 64-byte cache lines at lightning speed. For small arrays (N < 64), linear scan beats a hash map or binary search because there are zero hash collisions, no pointer indirection, and minimal branch mispredictions.
  2. Zero Preprocessing Overhead: Sorting an array takes O(n log n). If you only search the array once or twice, sorting it just to do binary search is an anti-pattern.
  3. Works on Streams & Linked Structures: Linear search operates seamlessly on data streams, files read chunk-by-chunk, and linked lists where instant random access by index (nums[mid]) is physically impossible.

Step-by-step execution walkthrough

1
Inspect Index 0

nums[0] = 4. Compare with target 7. 4 != 7. Advance pointer.

i = 0 (val: 4) != 7
2
Inspect Index 1

nums[1] = 2. Compare with target 7. 2 != 7. Advance pointer.

i = 1 (val: 2) != 7
3
Inspect Index 2

nums[2] = 7. Compare with target 7. 7 == 7. Match found!

i = 2 (val: 7) === target -> Return 2
Advantages
  • •Works on completely unsorted collections
  • •Requires zero additional memory overhead O(1)
  • •Extremely simple to implement with minimal CPU branch mispredictions for small arrays
Trade-offs
  • •Slow O(n) performance for large arrays with millions of elements
  • •Inefficient compared to O(log n) Binary Search when data is already sorted

Code Implementations

Copy & paste production-ready solutions for Sequential Scan (Single Pass) in your language of choice

File: solution.py
Python
def linear_search(nums: list[int], target: int) -> int:
    for i, num in enumerate(nums):
        if num == target:
            return i
    return -1
if __name__ == "__main__":
    nums = [4, 2, 7, 1, 9, 3]
    target = 7
    print("Found target at index:", linear_search(nums, target))
Interactive visualizer available

Understand Linear Search Visually

Scan elements sequentially one-by-one, comparing each value with the search target. Test live edge cases and watch memory state transitions step-by-step.

Launch Linear Search Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyBinary Search
Visualizer

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

2 approaches(O(log n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
MediumBinary Search
Visualizer

Search in Rotated Sorted Array

Search a rotated sorted array in O(log n) time. A masterclass in applying binary search when global order is broken: at least one half is always guaranteed to be sorted.

1 approach(O(log n))
Learn logic