Linear Search

Find the index of the first occurrence of a target value in an array using AVX2.

Return the index of the first element equal to target, or -1 if not found. This is the vectorized equivalent of std::find.

Function Signature

#include <immintrin.h>
#include <cstdint>

int linear_search(const int32_t* arr, int n, int32_t target);

Parameters:

• arr — pointer to an array of n signed 32-bit integers, guaranteed 32-byte aligned
• n — number of elements, guaranteed to be a multiple of 8 and at least 8
• target — the value to search for

Returns: the index of the first occurrence of target, or -1 if not found

Example

Input:  arr = [10, 20, 30, 40, 50, 60, 70, 80], target = 50
Output: 4

Constraints

• 8 ≤ n ≤ 4,000,000
• n is always a multiple of 8
• arr is 32-byte aligned
• There may be zero, one, or multiple occurrences of target

Notes

The key advantage of SIMD search is comparing 8 elements at once. When a match is found in a block, you need to determine which lane matched — this is where movemask and ctz (count trailing zeros) come in.

Unlike sum-based problems, search benefits from early exit: you can return as soon as the first match is found.

Useful Intrinsics