The C Programming Language, Ansi C
To illustrate a three-way decision, here is a binary search function that decides if a particular value x occurs in the sorted array v. The elements of v must be in increasing order. The function returns the position (a number between 0 and n-1) if x occurs in v, and -1 if not.
Binary search first compares the input value x to the middle element of the array v. If x is less than the middle value, searching focuses on the lower half of the table, otherwise on the upper half. In either case, the next step is to compare x to the middle element of the selected half. This process of dividing the range in two continues until the value is found or the range is empty.
/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low+high)/2;
if (x < v[mid])
high = mid + 1;
else if (x > v[mid])
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}
The fundamental decision is whether
x
is less than, greater than, or
equal to the middle element
v[mid]
at each step; this is a natural
for
else-if
.
Exercise 3-1. Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside.) Write a version with only one test inside the loop and measure the difference in run-time.
The
switch
statement is a multi-way decision that tests whether an
expression matches one of a number of
constant
integer values, and
branches accordingly.
switch (
expression
) {
case
const-expr
:
statements
case
const-expr
:
statements
default:
statements
}
Each case is labeled by one or more integer-valued constants or constant
expressions. If a case matches the expression value, execution starts at that
case. All case expressions must be different. The case labeled
default