04. Searching and Sorting

Search Contracts Come First#

A search takes a collection and a target key, and reports whether or where the target occurs. “Return an index” leaves an important ambiguity when duplicates exist: any matching index, or the first one? The analysis lecture initially specifies the first appearance. Ordinary binary search stops at a matching midpoint and does not necessarily satisfy that stronger contract. We will distinguish the two.

Linear Search: No Ordering Assumption#

int linearSearch(const int a[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target) return i;
    }
    return -1;
}

Require n >= 0 and n readable array entries when n > 0. On [12,5,19,5], searching for 5 compares 12 then returns index 1. Searching for 7 checks all four and returns -1. The invariant before iteration i is that no earlier entry equals the target. Thus returning i returns the first occurrence; reaching n establishes absence.

Watch the first matching value terminate this example. Change the target to an absent value to see the entire scan.

The time is constant for a match at index zero and linear for absence or a final-position match. Storage is unchanged and auxiliary space is constant. With no order or useful index, each unseen entry could still be the target, so an unsuccessful search must inspect all entries.

Practice. Why is return -1 inside the loop immediately after the if incorrect?

Binary Search: Eliminate an Entire Half#

Binary search requires an array sorted by the same comparison used for the target. It retains a candidate interval and compares the midpoint. If the midpoint is smaller than the target, all entries at or before it are too small; if larger, all entries at or after it are too large. Ordering is what makes discarding many unseen entries valid.

int binarySearch(const int a[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Here bounds are inclusive: both lo and hi are candidates. An empty array starts with hi = -1, so the loop performs no access. lo + (hi-lo)/2 avoids adding two potentially large indices. The +1 and -1 exclude the already tested midpoint and force progress.

On the lecture array, searching for 53 gives:

The original slide illustration shows a different informal sequence of four halvings. The explicit floor-midpoint code here finds 53 in two comparisons. Traces depend on midpoint and interval conventions; the logarithmic worst-case reasoning is the same. The figure above matches this code exactly.

Watch the bounds, discarded region and midpoint on this same input:

For absent 54, midpoint values are 110, 53, 78, then 67. The interval becomes lo=3, hi=2, which is empty; return -1. The invariant is that any occurrence not already ruled out lies in [lo,hi]. Every unequal comparison reduces the interval; termination without a match eliminates every possible location.

Practice. Trace target 9 in [1,3,5,7]. Why would updating lo = mid instead of mid+1 risk nontermination?

First Occurrence With Duplicates#

To retain the first-appearance contract, remember a match and keep searching left:

int binaryFirst(const int a[], int n, int target) {
    int lo = 0, hi = n - 1, answer = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            if (a[mid] == target) answer = mid;
            hi = mid - 1;
        }
    }
    return answer;
}

For [1,2,2,2,4], first compare index 2 and record it. Search 0..1: index 0 is too small; index 1 matches and replaces the answer. Return 1. Ordinary binary search would return 2, which is valid only for an any-match contract. This modified version continues after equality, so even its successful search generally takes logarithmic work.

After k halvings, at most about n/2^k candidates remain. Reaching at most one requires logarithmically many halvings; ordinary binary search has constant best-case and logarithmic worst-case time. The loop uses constant auxiliary space. Binary search on a singly linked list does not inherit constant-time midpoint access; finding midpoints by traversal destroys the array-style cost argument.

What Does It Mean to Sort?#

Sorting arranges a collection according to a key, the part of each item being ordered. A student record can contain a name, zID and WAM; sorting by WAM must carry the whole record along, not detach its WAM from its name. Require a consistent comparison relation: contradictory comparisons cannot define a meaningful sorted result.

Stability means equal-key items retain their original relative order. In the lecture example, the input is (90,Alice), (75,Bob), (90,Charlie), (75,Diana), (90,Eve). A stable ascending sort places Bob before Diana and Alice before Charlie before Eve:

Stability matters when the record has information beyond its key. If every item is just the integer 90, swapping two equal integers cannot visibly change the result. Label duplicates 90_A and 90_B when testing stability.

Sort by Multiple Keys#

Suppose names are already alphabetical. A stable sort by WAM preserves alphabetical names within equal WAMs. More generally, to obtain primary key P and secondary key S, first stably sort by S, then stably sort by P. The final primary sort groups equal P values without destroying the secondary order established inside those groups.

Practice. Initially (B,2), (A,2), (C,1). First sort by name, then stably by number. What is the result, and what could an unstable second sort destroy?

Adaptive and In-Place Algorithms#

An adaptive algorithm takes advantage of existing order. Insertion sort on an already sorted array performs one failed movement comparison per next item; little disorder means little shifting. A non-adaptive sort does essentially the same asymptotic work even on sorted input, such as standard merge sort. Merely having unequal times on two examples does not establish useful adaptation to existing order.

An in-place array algorithm rearranges items in their existing storage using small extra working state. Selection, bubble and insertion use constant auxiliary memory. Quicksort partitions in the array but still uses recursive stack memory, so the course's “in-place” description does not mean constant total auxiliary space. Merge sort uses an extra array. Always state which storage is counted.

Compare algorithms by key comparisons, movements and auxiliary storage, as well as best/average/worst time. A swap normally performs three assignments; shifting a sequence performs one assignment per shifted item plus a final insertion. Equal Big-Oh classes do not imply equal constant costs.

The lecture asks for three input cases when evaluating a sort. Already sorted and reverse sorted are concrete structured cases; random order needs a specified distribution before it supports an average or expected claim. For each case, count comparisons and movements separately: selection still scans every suffix on sorted input, insertion shifts nothing there, and a fixed-first-pivot quicksort can become worse there. Stability, adaptation and in-place storage are separate properties, so one favourable timing case does not prove all three.

Item Types and Comparison Helpers#

The slides use Item and comparison macros so the mechanism can be discussed separately from the key type. For integers:

typedef int Item;
#define lt(a, b) ((a) < (b))
#define le(a, b) ((a) <= (b))
#define gt(a, b) ((a) > (b))
#define ge(a, b) ((a) >= (b))

void swap(Item a[], int i, int j) {
    Item tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

For strings, strcmp(a,b) compares content; a < b compares pointer addresses and does not sort lexically. For records, compare the selected field but swap the whole Item. Avoid putting side effects such as i++ in macros whose arguments may be evaluated more than once. These notes use direct integer comparisons in implementations to keep each update visible.

Practice. You must preserve hiring order among employees with equal salary. What property is essential, and what extra question should you ask before choosing a sort?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Binary search is asked for the first occurrence of 7 in [2,7,7,7,9]. Why may ordinary equality-return search be wrong, and what index should the modified search return?

Question 2. A sort compares records only by surname. Two records have the same surname but different given names. What must the comparator do to sort lexicographically by both fields?

Question 3. You must repeatedly search a small array that changes after almost every query. Explain when sorting once for binary search might fail to help.