algorithmfree
Linear search
Check items one by one until you find the target. The simplest O(n) algorithm.
- time
- O(n)
- space
- O(1)
// step through it
step 1 / 5
1function linearSearch(nums, target) {2 for (let i = 0; i < nums.length; i++) {3 if (nums[i] === target) return i;4 }5 return -1;6}- target
- = 6
- n
- = 6
- checks
- = 1
- 7i
- 2
- 9
- 4
- 6
- 1
nums[0] = 7 is not 6. Checks so far: 1.
How it works
Linear search looks at every item in order. If the target is near the front it is fast, but in the worst case it checks all n items, so the work grows in step with the input: double the array, double the checks. That is what O(n) means. Watch the checks counter as you step.