Preconditions and Functions

Week 11 adds two things to the array programs of week 10. The first is a precondition: binary search only works on sorted data, and a program that assumes its input is sorted without checking will return confident nonsense on the day the input is not. The second is user-defined functions. The syllabus asks that the matrix program read and print its matrices through functions, which is chapter 9 arriving in the lab, and once the read and print loops live in functions the main program shrinks to the arithmetic and the checks, which is what a main program should be.

Program 1: Binary Search

Read N integers in ascending order and a key, and find the key by halving the search window each step.

Algorithm:

  1. Start.
  2. Read N, the N values, and the key, with the usual checks.
  3. If any value is smaller than the one before it, print that the array is not ascending and stop.
  4. Set lo to 0, hi to N − 1, and found to −1.
  5. While lo ≤ hi: set mid to the middle of lo and hi; if values[mid] is the key, set found to mid and stop looking; if values[mid] is less than the key, set lo to mid + 1; otherwise set hi to mid − 1.
  6. Report the index, or that the key is absent.
  7. Stop.

Type 10, then 2 5 8 12 16 23 38 56 72 91, then 23: found at index 5, after looking at index 4, then 7, then 5. Three comparisons for ten elements, where linear search would have taken six, and the gap widens with every doubling of N. Chapter 7 gave the reasoning: each comparison discards half of what is left, so the count of comparisons is the number of times N can be halved.

The check on step 3 is the precondition made executable. It walks the array once, and the moment a value is smaller than its predecessor it stops the program, because from that point on the halving argument is false and binary search can miss a key that is present. The check costs a linear pass, which sounds like it defeats the purpose; it does not, because the sortedness is verified once and the search can then run any number of times on the same data. Try 5, 1 3 2 4 5, and 3 to see it fire. Equal neighbours are allowed, since a non-decreasing array is still sorted; with duplicates the search reports an index holding the key, not necessarily the first, and an exam answer should say so.

Two details in the loop. mid is written as lo + (hi - lo) / 2 rather than (lo + hi) / 2. For an array of 100 the two are identical, but the sum form overflows when lo and hi are both above a billion, and the difference form never does; it costs nothing to write the safe one every time. And the window updates skip mid itself, mid + 1 and mid - 1, because mid has already been tested; write lo = mid and the window can stop shrinking once it is two elements wide: with the ten values above, searching for 100, or even for the 23 that is present, never terminates.

Program 2: Matrix Addition and Subtraction

Read two matrices, check that they have the same shape, and print both together with their sum and difference. The reading and printing are done by functions.

Algorithm:

  1. Start.
  2. Read the rows and columns of A; if either is outside 1 to 10, print a message and stop. Read A's elements.
  3. Read the rows and columns of B with the same check. If they differ from A's, print that the matrices are not compatible and stop. Read B's elements.
  4. For each row and column, sum = A + B and difference = A − B.
  5. Print A, B, the sum, and the difference, each under a heading.
  6. Stop.

Enter 2 3, then 1 2 3 and 4 5 6, then 2 3, then 6 5 4 and 3 2 1. The sum is a matrix of sevens and the difference runs from −5 to 5.

The two functions are the point of the program. readMatrix fills a matrix and reports whether every read succeeded, returning 1 or 0 so that main can decide what to do about a failure; a void reader that printed its own error and carried on would leave main computing with half a matrix. printMatrix prints rows with the space-before-every-element-but-the-first rule from week 10, and the headings stay in main, because the function's job is the matrix, not the label. Both are declared before main with full prototypes and defined after it, the chapter 9 layout.

The parameter int m[MAX][MAX] is how a two-dimensional array reaches a function in C, and chapter 11 explained why the second dimension is not optional: the function receives a pointer to the first row, and to find row i it must know how long a row is, which is the column count baked into the type. That is also why the arrays are declared with the fixed MAX in both dimensions and the real size travels separately as rows and cols. The compatibility check compares those real sizes; an int m[][] parameter with no dimensions at all does not compile.

Compatibility is checked as soon as B's dimensions are known, before its elements are read, so an incompatible pair is refused without reading numbers that will never be used. The sum and difference are computed in one pass in main, since they walk the same cells; a third function, addMatrices, would be the next refactoring and is a fair viva question.

Key Takeaways

  • Binary search requires sorted input; check the precondition with one linear pass and refuse an unsorted array rather than searching it.
  • mid = lo + (hi - lo) / 2 never overflows; the window updates must skip mid with mid + 1 and mid - 1.
  • With duplicates, binary search finds an index holding the key, not necessarily the first.
  • A function that reads input returns a status so that main can stop on failure; a void reader hides the error.
  • A two-dimensional array parameter must carry its column count, int m[MAX][MAX], so the function can locate rows; pass the real sizes separately.
  • Check matrix compatibility as early as the dimensions are known, before reading elements that will not be used.