2015-02-13

Time required for a program segment with a loop depends on the number of
times the loop is executed. The simplest case is the time required for the
linear search of an array. See
10
Feb. While the time required to* find* something
obviously varies from immediately (in

Sorting gives us a nested loop. Here is an implementation of the selection sort demonstration program from 12
Feb. with the "find index of largest" logic imbedded in the sort itself:

SelectionSort.txt SelectionSort.c
SelectionSort.exe

The loop `for (lim = n; lim > 1 ; )` executes `n-1` times. For each value of `lim` the nested
loop `for (ck = 1; ck < lim; ck++)` executes `lim-1` times.
This ties into a famous formula:

The sum of all the integers from 1 up to n is given by n * (n+1) / 2.
Since we're talking about ratios we simplify this to O(n^{2}) and call
it quadratic complexity.

Finally, a simple example of nesting three loops:

Triple.txt Triple.c
Triple.exe

We see that finding something in an array by examining individual cells required linear time. But what if the array is sorted?

Let's look at a number guessing game, with only Goldilocks clues:
too low, too high, and* just right.* This is a program from
the Winter 2014 quarter.

numberGuess.txt numberGuess.c numberGuess.exe

The optimal strategy, in this case, is to always check in the middle of the known too-low and too-high values.

Please enter a number between 1 and 100 inclusive 50 Too High - You have 9 tries left Please enter a number between 1 and 100 inclusive 25 Too High - You have 8 tries left Please enter a number between 1 and 100 inclusive 12 Too Low - You have 7 tries left Please enter a number between 1 and 100 inclusive 18 You Got it Play again (y/n) n

If the array is sorted, then searching for a value can take advantage of this strategy: each pass through the loop is guaranteed to discard half of the array segment being considered.

It is referred to (for obvious reasons) as binary search:

// Binary search. x[] is presumed to be sorted. int BinSrch (int x[], int n, int sought) { int lo = 0, hi = n-1, mid; // On average, 1 1/2 comparisons per loop iteration while (lo <= hi) // Note return WITHIN the loop. { mid = (lo + hi) / 2; if (sought > x[mid]) lo = mid + 1; else if (sought < x[mid]) hi = mid - 1; else return mid; // Early exit on success } return -1; // Fail-to-find flag }

Note: in this demonstration implementation, there is the option of
seeing every step of the binary search (if `DEBUG` has been `#define`d as non-zero).

BinSrch.txt BinSrch.c
BinSrch.exe