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.
#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 alignedn — number of elements, guaranteed to be a multiple of 8 and at least 8target — the value to search forReturns: the index of the first occurrence of target, or -1 if not found
Input: arr = [10, 20, 30, 40, 50, 60, 70, 80], target = 50
Output: 4
8 ≤ n ≤ 4,000,000n is always a multiple of 8arr is 32-byte alignedtargetThe 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.
| Intrinsic | Description |
|---|---|
_mm256_load_si256(ptr) | Load 256 bits from aligned memory |
_mm256_set1_epi32(x) | Broadcast a 32-bit integer to all lanes |
_mm256_cmpeq_epi32(a, b) | Compare packed 32-bit integers for equality |
_mm256_castsi256_ps(v) | Reinterpret integer vector as float (free, no conversion) |
_mm256_movemask_ps(v) | Extract sign bits into an 8-bit mask |
__builtin_ctz(x) | Count trailing zeros (index of lowest set bit) |
Output will appear here after you run or submit.