linear search
Linear search is the most honest way to find something in a list: start at the front and check each item in turn, one after another, until you either find what you're looking for or run off the end. It's exactly how you'd hunt for a friend's name on an unsorted guest list — eyes down the page, top to bottom.
Because it makes no assumptions, linear search works on any collection, sorted or not, and on any structure you can walk through one element at a time — an array, a linked list, a file read line by line. That generality is its charm: there is nothing to set up and nothing that can go wrong.
The cost is that you may have to look at everything. In the worst case the target is the last element (or absent), so you do n comparisons — O(n) time. On average, for a present target, you scan about half the list, still O(n). It uses no extra memory, O(1) space. When data is unsorted, or so small that cleverness isn't worth it, linear search is often the right and simplest choice.
int linearSearch(const std::vector<int>& a, int target) {
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] == target) return i; // found it
return -1; // not present
}Every element may need a look, so the worst case is n comparisons — O(n).
If the data is already sorted, binary search beats linear search dramatically — O(log n) versus O(n). Sort first only if you'll search many times; sorting once costs O(n log n).