Easy difficulty · Algorithm · Topics: searching, array, brute-force
Linear search finds a target value in an array by checking the elements one at a time, from the first to the last. It returns the index of the first match, or -1 when the value is not there. It needs no preparation of the data, so it works on any array, sorted or not.
Think of looking for a name on a printed list by running your finger down it. You do not need the list to be in any order: you just keep going until you see the name or run out of lines. The algorithm is exactly that. The invariant is simple: before looking at index i, we know the target is not in nums[0..i-1]. When the loop ends without a hit, that fact covers the whole array.
i = 0.nums[i] with target.i immediately.i + 1.i runs past the last element, return -1.Test case 0: nums = [7, 3, 9, 4, 1, 8], target = 4.
| Step | i | nums[i] | Equal to 4? | Action |
|---|
| 1 | 0 | 7 | no | move on |
| 2 | 1 | 3 | no | move on |
| 3 | 2 | 9 | no | move on |
| 4 | 3 | 4 | yes | return 3 |
The elements 1 and 8 are never examined, because the search stops at the first match.
| Case | Time | Why |
|---|---|---|
| Best | O(1) | the target is the first element |
| Average | O(n) | about half of the array is scanned |
| Worst | O(n) | the target is last or missing, so every element is checked |
| Space | O(1) | only the index i is stored |
<= in the loop condition reads nums[nums.length], which is undefined.false, null or 0 for "not found". 0 is a valid index, so -1 is the usual sentinel.== instead of === can match values of different types (for example "4" and 4).i as it moves one bar to the right per step.nums[i] === target is the only work per step. Watch the target variable stay constant while i changes.i walks to the end and the result is -1.Input: nums = [7, 3, 9, 4, 1, 8], target = 4
Output: 3
class Solution {
linearSearch(nums, target) {
// Look at every position from left to right.
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
return i; // found: report the index
}
}
return -1; // checked everything, not present
}
}