Linear Search from Scratch: How Array Contains Works
Before you reach for arr.includes() or a hash set, it's worth understanding exactly what happens when you search an unsorted array. The answer is a linear scan — checking each element one by one until you find a match or exhaust the array. This is called linear search, and it's the foundation of countless algorithms. Writing it yourself makes you a better programmer even when built-ins are available.
Why Not Just Use includes()?
The problem explicitly asks you to implement the check yourself. That's because includes() hides the loop — you don't see the O(n) cost, you don't practice loop structure, and you don't understand when a faster approach (like binary search on a sorted array, or a Set for repeated lookups) would be worthwhile. Once you've built it manually, using includes() in production code is the right call — but you'll know what it's actually doing.
The Early-Exit Pattern
The key insight in linear search: return as soon as you find a match. Don't keep scanning after the answer is found. This is called an early exit (or early return), and it makes your code both faster and cleaner.
Code Implementation
function contains(nums, value) {
// Iterate through each element in the array
for (let i = 0; i < nums.length; i++) {
// Check if the current element matches the given value
if (nums[i] === value) {
return true; // Return true if a match is found
}
}
return false; // Return false if no match is found
}
// Test cases
console.log(contains([1, 2, 4, 5], 4)); // true
console.log(contains([-1, 2, -4, 0, 10], 7)); // false
Complexity Analysis
The time complexity of this approach is O(n), where n is the number of elements in the array. This is because we may need to check each element once. The space complexity is O(1) since we are not using any additional space that scales with the input size.
Edge Cases
Consider the following edge cases:
- An empty array: The function should return
false. - An array with one element: The function should correctly identify if the single element matches the value.
- Multiple occurrences of the value: The function should return
trueas soon as it finds the first match.
Examples:
contains([], 1) -> false contains([1], 1) -> true contains([1, 2, 3, 1], 1) -> true
Tracing Through an Example
// contains([1, 2, 4, 5], 4)
// i=0: nums[0]=1, 1 !== 4 → continue
// i=1: nums[1]=2, 2 !== 4 → continue
// i=2: nums[2]=4, 4 === 4 → return true ✓
// Never checks index 3 — early exit saves one comparison
Complexity Analysis
- Time: O(n) — worst case scans every element. Best case O(1) if the value is first.
- Space: O(1) — just one loop variable regardless of array size.
Key Takeaways
- Linear search iterates through each element and returns
truethe moment it finds a match. - Time: O(n). Space: O(1). This is optimal for unsorted arrays.
- Use
return trueinside the loop (early exit) — don't scan past the first match. - In production JavaScript, use
arr.includes(value)— it does exactly this, with a clean API.
What to Learn Next
Now that you understand linear search, level up to binary search — which achieves O(log n) by requiring the array to be sorted first. Then explore JavaScript's Set for O(1) average-case membership checks when you'll be searching the same collection repeatedly. Finally, see how this search pattern extends to objects using Object.keys() and Map.has().
