Searching, sorting and algorithm efficiency

Linear search

Check each element in turn. Works on unsorted data, needs no preparation, but on average examines half the list and in the worst case all of it — $O(n)$.

Binary search

Requires a sorted list. Compare the middle element; if the target is larger discard the lower half, if smaller discard the upper half, and repeat. Each comparison halves the remaining data, so the worst case is $O(\log_2 n)$: $1\,000\,000$ items need about $20$ comparisons. The precondition is the whole point — a binary search on unsorted data returns wrong answers, not slow ones.

Bubble sort

Repeatedly pass through the list swapping adjacent elements that are out of order; after each pass the largest remaining value has 'bubbled' to the end. A flag that records whether any swap occurred lets it stop early on nearly sorted data. Simple to code, but $O(n^2)$.

Insertion sort

Take each element and insert it into its correct place among those already sorted. Also $O(n^2)$, but usually faster than bubble sort in practice and very fast on nearly sorted data.

Talking about efficiency properly

Big-O describes how run time grows with input size, not the actual time. Doubling $n$ roughly doubles the work of an $O(n)$ algorithm and quadruples that of an $O(n^2)$ one — that difference is invisible at $n=10$ and decisive at $n=100\,000$. Also consider memory: an algorithm that is faster but needs a second copy of the data may not fit.

Choosing

Sort once and search many times, and the cost of sorting is repaid by binary searches. Search a small list once, and a linear search on unsorted data is the right answer.