Linear Search

Linear search finds a target value in an array by checking elements one at a time, from the first index to the last, and stopping the moment one matches. It makes no assumptions about the data — the array can be in any order — so its time complexity is O(n): in the worst case it looks at every element.

This is the search you already do by hand. Hunting for a name on an unsorted guest list, you start at the top and read down until you hit it. You cannot jump to the middle and rule out half, because nothing about position tells you anything about value — the list isn't sorted. That single fact is the whole trade-off of linear search: it asks nothing of the input, and in return it can do no better than reading the whole thing.

How Linear Search Works: Check Each Element, Stop at the First Match

Walk a cursor i from 0 to n − 1. At each step, compare nums[i] with the target:

• Equal → you found it. Return i immediately and stop. Nothing after i needs to be looked at.
• Not equal → this element is ruled out. Move the cursor one step right and try again.

If the cursor runs off the end without a match, the target is not in the array; return −1.

Two design decisions do the real work. The early return is what makes a hit cheap: the scan stops the instant it matches, so it never inspects the elements past the target. And because the loop only ever reads values — never compares positions — the array needs no particular order. Sort it, shuffle it, reverse it; linear search still finds the target. Reordering can move the first match, so the returned index and the comparison count may change, but the answer stays correct. That is exactly what binary search cannot claim, and exactly why you reach for linear search when the data isn't sorted.

Linear Search Step by Step

The default input is nums = [42, 17, 8, 91, 23, 4, 56, 30] with target = 23. Notice the array is not sorted — it doesn't need to be.

1. i = 0: nums[0] = 42. 42 ≠ 23, so 42 is ruled out. Advance.
2. i = 1: nums[1] = 17. 17 ≠ 23. Advance.
3. i = 2: nums[2] = 8. 8 ≠ 23. Advance.
4. i = 3: nums[3] = 91. 91 ≠ 23. Advance.
5. i = 4: nums[4] = 23. 23 == 23 — match. Return index 4 and stop.

Five comparisons for a hit at index 4. The three elements after it — 4, 56, 30 — are never examined, because the scan returned the instant it matched.

On the canvas, the i cursor slides left to right one cell at a time. The cell under the cursor lights up amber while it is being compared; each rejected cell fades out behind the cursor, so the trail of faded cells shows exactly how far the search has looked. When the target is reached its cell turns green and the cursor stops there — and the cells to its right stay at full strength, un-faded, a visible reminder that the search never touched them.

Time and Space Complexity: Cost Is the Target's Position

The cost is the target's position: a hit at index k costs k + 1 comparisons, and a miss costs all n. That is the number the player prints on screen as the cursor moves, so you can watch it climb. Space is O(1) — a single index and no extra structures.

When to Reach for Linear Search

Reach for it when the array is unsorted and the lookup is one-off, when the collection is small enough that O(n) is trivially fast, or when the structure can only be walked forward — a linked list has no random access, so binary search isn't even an option. Reach for something else when you will query the same collection repeatedly: a hash set answers membership in O(1) average after an O(n) build, and if the data is sorted, binary search finds a position in O(log n) — twenty comparisons for a million elements against linear search's million. Linear search is the honest default you outgrow the moment lookups repeat or the data earns structure.

Edge Cases

• Empty array — the loop body never runs; return −1 without a single comparison. (This is the code's behavior; the interactive player starts inputs at five elements, so the sandbox does not demonstrate it.)
• Target at the first index — one comparison, then stop. This is the best case, O(1).
• Target at the last index, or absent — the cursor walks the entire array. These are the worst cases, and they cost the same n comparisons; the only difference is whether the last comparison matches.
• Duplicate targets — linear search returns the index of the first match, because the early return fires the moment it sees one. The copies further right are never reached.

Common Mistakes

• Dropping the early return. If the loop keeps going after a match — say it records the index but doesn't return — it stops finding the first occurrence and instead reports the last, and it always pays the full n comparisons even when the answer was at index 0. The early return is what makes a hit cheap and first-wins; it is not an optional optimization.
• Assuming the input must be sorted. It doesn't need to be. Sortedness buys binary search its speed, but linear search needs nothing of the kind — sorting first just to run one scan wastes the sorting work, and it doesn't make the scan any faster on average. If your data happens to be sorted and you care about performance, that is the signal to switch algorithms, not to keep scanning.
• Scanning a collection you query over and over. A single linear scan is fine; a linear scan repeated on every lookup is the mistake — that is when a hash set (O(1) average membership) or a sorted array with binary search earns its keep. See When to Reach for Linear Search above.
• Forgetting the −1 sentinel. Falling off the end of the loop is a real outcome, not an error. Return a value the caller can test for (−1, None, an option type) so "not found" is distinguishable from "found at index 0."