Linear Search

Linear search has no shortcuts because it has no information. An unsorted array gives you nothing to rule out, so the only honest way to find a target is to look at each element and ask: is this it? The algorithm walks the array from index 0, comparing the target to the current element. The moment they match, it stops and reports the index. If it reaches the end without a match, it reports that the target is not there, often with -1.

That -1 matters because it is a signal, not a position. Returning 0 would look like a real index, as if the target sat at the front of the array, but -1 can never be mistaken for a location since valid indices never go negative. Mixing these up is a common source of bugs when code checks the result of a search and tries to use it as an index without first checking for -1.

Counting comparisons makes the behavior concrete. If the target sits at position k (counting from 1), linear search makes exactly k comparisons, since it checks one element at a time from the start and stops the instant it matches. If the target is missing from an array of n items, the algorithm must check all n before concluding that, so it makes exactly n comparisons. This connects directly to binary search, which only works on sorted data but cuts the array in half each step instead of checking one element at a time, and to 2D arrays, where linear search has to sweep every row, treating the grid as one long sequence of elements to check.