Week 3: Binary Search & Sorting

1. Binary Search on a Sorted Array

Binary search halves the remaining search space on every step by comparing the target against the middle element, giving O(log n) time instead of O(n) for a linear scan. Getting the loop invariants exactly right — inclusive vs. exclusive bounds — is what separates a binary search that works from one that infinite-loops or misses the answer by one:

binary_search.cpp

#include <vector>
using namespace std;

// Classic "find the exact value" binary search. O(log n) time, O(1) space.
int binarySearch(const vector<int>& sorted, int target) {
    int lo = 0, hi = (int)sorted.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // avoids overflow vs. (lo + hi) / 2
        if (sorted[mid] == target) return mid;
        else if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// First index where sorted[idx] >= target (a "lower bound"). If target is bigger
// than every element, returns sorted.size(). O(log n) time.
int lowerBound(const vector<int>& sorted, int target) {
    int lo = 0, hi = (int)sorted.size();   // hi is exclusive here
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

The STL already provides lower_bound and upper_bound in <algorithm>, which do exactly this over any sorted range in O(log n):

stl_bounds.cpp

#include <vector>
#include <algorithm>
using namespace std;

vector<int> nums = {1, 3, 3, 3, 5, 7};
auto lo = lower_bound(nums.begin(), nums.end(), 3);  // iterator to first 3
auto hi = upper_bound(nums.begin(), nums.end(), 3);  // iterator just past the last 3
int countOfThrees = (int)(hi - lo);                  // 3

Always write mid as lo + (hi - lo) / 2

Writing (lo + hi) / 2 can overflow int when both bounds are large, even though each is individually a valid index. It's a real bug that has shown up in production code — lo + (hi - lo) / 2 computes the identical midpoint without ever summing two large values.

2. Binary Search on an Answer Space

Binary search doesn't require an array at all — it only requires a monotonic predicate: a yes/no question where, as you scan candidate answers from low to high, the answer flips from false to true (or true to false) exactly once. Whenever a problem says "minimize the maximum" or "maximize the minimum," that's usually a signal to binary search over the space of possible answers rather than over an array.

A classic example: split an array into k contiguous parts to minimize the largest part's sum. Instead of searching for the split points directly, binary search on the answer itself — the value of that largest sum — and use a greedy feasibility check to test each candidate:

split_array_minimize_max.cpp

#include <vector>
#include <algorithm>
using namespace std;

// Can nums be split into <= k contiguous parts so that every part's sum <= cap?
// Greedy: keep adding to the current part until adding the next element would
// exceed cap, then start a new part. O(n) per call.
bool canSplit(const vector<int>& nums, int k, long long cap) {
    int parts = 1;
    long long currentSum = 0;
    for (int x : nums) {
        if (currentSum + x > cap) {
            parts++;
            currentSum = x;
            if (parts > k) return false;
        } else {
            currentSum += x;
        }
    }
    return true;
}

// Minimum possible value of the largest part's sum, when splitting nums into k parts.
// The answer space is [max(nums), sum(nums)] and canSplit is monotonic over it:
// once a cap is feasible, every larger cap is feasible too. O(n log(sum)) overall.
long long splitArrayMinimizeLargestSum(const vector<int>& nums, int k) {
    long long lo = *max_element(nums.begin(), nums.end());
    long long hi = 0;
    for (int x : nums) hi += x;

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canSplit(nums, k, mid)) hi = mid;   // mid works -- try to do better
        else lo = mid + 1;                       // mid too small -- need more room
    }
    return lo;
}

Sanity-check monotonicity before you code

Before writing a binary-search-on-answer solution, explicitly convince yourself the feasibility function is monotonic — that every value above (or below) some threshold is feasible and every value on the other side is not. If it isn't monotonic, binary search will silently return a wrong answer instead of erroring, which makes this bug easy to miss.

3. Merge Sort From Scratch

Merge sort splits the array in half recursively until each piece has one element (trivially sorted), then merges sorted halves back together in linear time. Its worst-case time complexity is guaranteed O(n log n) — there's no bad input that degrades it, which is exactly why it's the standard choice when a guarantee matters more than average-case speed:

merge_sort.cpp

#include <vector>
using namespace std;

// Merges the two already-sorted halves nums[lo..mid] and nums[mid+1..hi] into one
// sorted range, using a temporary buffer. O(hi - lo) time and space.
void merge(vector<int>& nums, int lo, int mid, int hi) {
    vector<int> temp(hi - lo + 1);
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= hi) temp[k++] = nums[j++];
    for (int x = 0; x < (int)temp.size(); x++) nums[lo + x] = temp[x];
}

// Sorts nums[lo..hi] in place. O(n log n) time, O(n) auxiliary space, stable.
void mergeSort(vector<int>& nums, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, lo, mid);
    mergeSort(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}

Because merge always takes the smaller of nums[i] and nums[j] when they're equal from the left half first, merge sort is stable — elements that compare equal keep their original relative order. That property matters when you're sorting by one key but need to preserve the order established by a previous sort on another key.

4. Quicksort From Scratch

Quicksort picks a pivot, partitions the array so everything smaller than the pivot ends up to its left and everything larger ends up to its right, then recurses on each side. Unlike merge sort, it sorts in place — no auxiliary array — but its worst-case time complexity is O(n²), which happens when the pivot choice repeatedly splits the array as unevenly as possible (e.g. always picking the last element on an already-sorted array):

quicksort.cpp

#include <vector>
using namespace std;

// Lomuto partition scheme: places nums[hi] (the pivot) in its final sorted
// position and returns that index. Everything left of it is < pivot,
// everything right is >= pivot.
int partition(vector<int>& nums, int lo, int hi) {
    int pivot = nums[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (nums[j] < pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i + 1], nums[hi]);
    return i + 1;
}

// Average case O(n log n) time, O(1) extra space (O(log n) recursion stack).
// Worst case O(n²) time if the pivot is consistently a poor split.
void quickSort(vector<int>& nums, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(nums, lo, hi);
    quickSort(nums, lo, p - 1);
    quickSort(nums, p + 1, hi);
}

The fix used in practice is to pick the pivot randomly (or via median-of-three) instead of always taking a fixed position, which makes the O(n²) worst case astronomically unlikely for any specific input an adversary or test case could construct:

randomized_pivot.cpp

#include <vector>
#include <cstdlib>
using namespace std;

int partitionRandomized(vector<int>& nums, int lo, int hi) {
    int randomIndex = lo + rand() % (hi - lo + 1);
    swap(nums[randomIndex], nums[hi]);   // move a random element into the pivot slot
    return partition(nums, lo, hi);      // reuse the same partition logic
}

Know when to reach for which

In an interview, std::sort (introspection sort, effectively quicksort with safeguards) is almost always what you'd actually call. What interviewers are testing when they ask you to implement sorting from scratch is whether you understand the trade-off: quicksort is faster in practice and in-place, merge sort gives you a worst-case guarantee and stability. Say both, and say why you'd pick one over the other for the problem at hand.

5. std::sort With Custom Comparators

std::sort from <algorithm> is a highly-tuned hybrid sort (typically introsort: quicksort with a heapsort fallback) that runs in O(n log n) average and worst case. Its real power for interviews is the optional comparator argument, which lets you sort anything by any rule you can express as a function:

custom_comparators.cpp

#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Employee {
    string name;
    int salary;
};

int main() {
    vector<Employee> emps = {{"Ana", 90000}, {"Bo", 75000}, {"Cy", 90000}};

    // Sort by salary descending, tie-break by name ascending.
    // The comparator must return true iff `a` should come strictly before `b`.
    sort(emps.begin(), emps.end(), [](const Employee& a, const Employee& b) {
        if (a.salary != b.salary) return a.salary > b.salary;
        return a.name < b.name;
    });

    // pair's default operator< compares .first, then .second -- sorts intervals
    // lexicographically with zero extra code.
    vector<pair<int, int>> intervals = {{1, 3}, {2, 6}, {8, 10}};
    sort(intervals.begin(), intervals.end());
}

A comparator must be a strict weak ordering

Your comparator must return false when two elements are equal — never use <= or >= in a comparator. Violating this (a comparator that isn't a strict weak ordering) is undefined behavior in std::sort: it can crash, throw, or silently corrupt the sort instead of just sorting "wrong."

6. Hands-on Exercise

Hands-on

Build and benchmark a sorting & search toolkit

Implement both classic sorts from scratch, wire up binary search on an answer space, and confirm everything agrees with the STL.

Requirements:

Implement mergeSort(vector<int>& nums) as a public wrapper around the recursive merge/mergeSort helpers.
Implement quickSort(vector<int>& nums) using the randomized-pivot partition so it doesn't degrade to O(n²) on already-sorted input.
Implement lowerBound and upperBound, then use them to implement countOccurrences(nums, target) in O(log n) as upperBound - lowerBound.
Implement splitArrayMinimizeLargestSum using binary search on the answer, and verify it against a brute-force check on small inputs.
Generate a random vector<int> of 20,000 elements, sort separate copies with your mergeSort, your quickSort, and std::sort, and assert all three produce identical output.
Time all three sorts with <chrono> on both random data and already-sorted data, and note where your naive (non-randomized) quicksort would have struggled.

Hint

To see the O(n²) worst case concretely, temporarily swap your randomized partition back to always picking nums[hi] and run it on an already-sorted array of 5,000+ elements — you should see it take dramatically longer (or blow the recursion stack) compared to the randomized version on the same input.

7. Knowledge Check

Four quick questions. Expand each to check your answer.

Why is merge sort's worst-case time complexity guaranteed O(n log n) while quicksort's worst case is O(n²)?

Merge sort always splits the array exactly in half regardless of the data, so its recursion depth is always log n and each level does O(n) work merging — that split is data-independent, so the guarantee holds for every input. Quicksort's split depends on where the pivot lands relative to the rest of the data; if the pivot is consistently the smallest or largest remaining element (e.g. a fixed-position pivot on already-sorted data), one side of the partition is empty and the recursion degrades to n levels instead of log n, giving O(n²).

What monotonic property must hold for binary search on an answer space to be valid, and what happens if it doesn't?

The feasibility check must be monotonic across the answer range — every candidate answer on one side of some threshold must be feasible, and every candidate on the other side must not be, with no feasible/infeasible values interleaved. If that property doesn't hold, discarding half the search space based on one feasibility check can throw away the true answer, so binary search will run to completion and return a wrong value without any error or crash to indicate the mistake.

Why must a comparator passed to `std::sort` return `false` when two elements are equal, rather than `true`?

std::sort requires its comparator to define a strict weak ordering, which means "is a strictly before b" — for equal elements, neither should be considered strictly before the other, so the comparator must return false in both directions. If a comparator returns true for equal elements (e.g. by using <= instead of <), it violates this contract, and the standard leaves the resulting behavior undefined — which in practice can mean out-of-bounds access or a crash, not just a slightly wrong order.

Compare the space complexity of merge sort and in-place quicksort. When would you prefer merge sort despite that difference?

Merge sort uses O(n) auxiliary space for the temporary merge buffers, while quicksort partitions in place and only needs O(log n) extra space for its recursion stack (with a good pivot strategy). Despite using more memory, you'd prefer merge sort when you need a guaranteed worst-case time bound (e.g. in a system with hard latency requirements), when stability matters (preserving the relative order of equal elements), or when sorting a linked list, where merge sort's sequential-access pattern works well and quicksort's random-access partitioning does not.