Every program looks things up and puts things in order. The two tasks seem similar. They reward different strategies.
Searching finds an item that satisfies a condition. Sorting arranges all items by a key. Sorting is rarely the goal. It is the purchase of a precondition called order.
Order pays off when you spend it many times. Thousands of lookups, range queries, and merge joins all draw on it. A one-shot scan never earns the price back.
What binary search buys and what it costs
Order lets each comparison eliminate half the candidates. Searching n elements then costs O(log n) comparisons instead of O(n):
n = 1,000,000 -> at most 20 comparisons
n = 1,000,000,000 -> at most 30 comparisonsA billion rows need only ten more comparisons than a million. That slow growth is the whole prize.
But sorting charges upfront. Sorting a million integers takes on the order of 100 milliseconds. Scanning the same million takes about 1 millisecond. The sort pays for itself only after hundreds of lookups.
Do that arithmetic before adding a sort to a path that runs twice a day. One scan at 1 millisecond beats a 100-millisecond setup every time.
A sorted array also enables range questions. "All orders between March and June" becomes two binary searches plus one slice. An unsorted pile answers the same question only by checking everything.
One binary search written carefully in three languages
Hand-written binary search hides classic bugs. The midpoint can overflow. The loop bounds can skip the last element. Absent and duplicated targets need deliberate handling.
The version below avoids all three traps. It computes the middle as lo + (hi - lo) / 2, which never overflows. It keeps the loop running while lo <= hi, so the final element gets checked. It returns -1 for absent targets.
#include <vector> // Search a sorted array for target and return its index. // Return -1 when the target is absent. int binarySearch(const std::vector<int>& a, int target) { // The target, if present, lies between lo and hi. int lo = 0; int hi = (int)a.size() - 1; while (lo <= hi) { // Overflow-safe middle: never adds two large indexes directly. int mid = lo + (hi - lo) / 2; if (a[mid] == target) return mid; // middle holds the target if (a[mid] < target) lo = mid + 1; // discard the left half else hi = mid - 1; // discard the right half } return -1; // range exhausted: the target is absent }
In production C++ code, prefer the standard search. std::lower_bound returns the first element not less than the key. It handles duplicates and gives the insertion position for free. Writing your own is a learning exercise, not a shipping habit.
Sorting algorithms share a floor but differ in constants
No comparison-based sort beats Ω(n log n) in the worst case. Each comparison yields one bit of information. Ordering n items needs enough bits to distinguish n! arrangements. The math forces about n log n comparisons.
Within that floor, behavior differs widely:
| Sort | Average | Worst case | Stable | Best use |
|---|---|---|---|---|
Introsort (std::sort) | O(n log n) | O(n log n) | no | general default |
| Merge sort | O(n log n) | O(n log n) | yes | linked lists, stable needs |
| Insertion sort | O(n²) | O(n²) | yes | tiny or nearly sorted input |
| Counting and radix | O(n + k) | O(n + k) | possible | bounded integer keys |
Introsort starts as quicksort, switches to insertion sort below about 16 to 32 elements, and falls back to heapsort if recursion runs deep. Each switch covers another method's weakness.
Non-comparison sorts escape the floor by refusing to compare. Counting sort tallies key frequencies into buckets. Radix sort orders by digits from least to most significant. Both need keys with bounded structure, such as bytes or fixed-width integers.
Stability protects earlier work from later sorts
Stability means equal elements keep their original relative order. A stable sort never scrambles ties. An unstable one may.
Stability matters whenever you sort twice. Sort employees by hire date, then by department, with a stable second sort. Each department group stays in hire-date order. An unstable second sort shuffles within groups unpredictably.
The bug surfaces as flaky interfaces and nondeterministic batch output. Rows with equal keys appear in a different order on each run. Tests pass on Monday and fail on Tuesday.
Stability costs almost nothing. Merge sort and std::stable_sort provide it directly. Request it whenever a later sort must preserve an earlier one.
Mistakes that cost real systems real time
Sorting a collection to search it once wastes the setup. The 100-millisecond sort dwarfs the 1-millisecond scan. Reserve sort-first for workloads with hundreds of lookups.
Maintained sorted indexes rot under writes. Each insert into a sorted array shifts a suffix at O(n). A workload with steady inserts usually needs a tree or a hash structure instead.
Duplicate keys turn points into ranges. Equal elements occupy the interval from lower_bound to upper_bound, not one index. Code that treats the range as a single position mishandles every repeated key.
Huge inputs change the bottleneck from comparisons to disk passes. External sort splits data into memory-sized runs, sorts each, and merges. Minimizing passes over the disk beats shaving comparisons.
Where search and sort run and what to read next
Databases sort for merge joins and binary-search their indexes. Contact lists keep one sorted copy for prefix lookup. Leaderboards update a heap for the top entries and sort only on display.
The decision pattern stays constant. Ask what the data already guarantees. Ask which operations must run fast. Ask how large n grows in production. Then pick the cheapest structure that meets all three answers.
Watch the searching and sorting trace to see both strategies execute. Test edge cases with practice: binary search boundary. Drill the standard form with practice: implement binary search.