Searching and Sorting

Searching Strategies

Searching (finding an item) and sorting (ordering items) are fundamental algorithmic tasks that make complexity theory practical.

Linear search scans every element one by one, taking $O(n)$ time. It works on any list, whether sorted or not.

Binary search repeatedly halves a sorted list by comparing the target to the middle, taking $O(\log n)$ time.

Common Pitfall: Applying binary search to an unsorted list yields wrong answers. It discards half the data assuming order, so it skips the target. Sort first or use linear search.

Sorting and Trade-offs

Sorting arranges elements into order. Simple methods like bubble sort, selection sort, and insertion sort run in $O(n^2)$ time — fine for small data, but slow at scale.

Efficient methods like merge sort and quicksort run in $O(n \log n)$ time, the limit for comparison-based sorting. They use divide and conquer: split data, sort recursively, and combine.

Sorting once lets you binary-search repeatedly. Choosing an algorithm depends on data size and how often you run the task.