Java Reference
In-Depth Information
/** = index of minimum value of b[h..k] . Precondition: h ≤ k. */
public static int min( int [] b, int h, int k)
Calling this function makes sense only if the array segment has at least one
value; hence the precondition.
How will this function be used? Examples when d={1 , 5 , 1 , 7 , 3 , 8} :
To watch this
algorithm exe-
cute, listen to
activity 8-5.3.
call
result
min(d , 0 , 5)
0 or 2
min(d , 1 , 5)
2
min(d , 3 , 5)
4
min(d , 1 , 1)
1
The call min(d , 0 , 5) is interesting: the specification does not say which mini-
mum value will be returned if the minimum value occurs more than once.
The heart of this function is a loop to find the index m of a minimum value.
We now develop it. Because we are allowed to return the index of any smallest
value, we choose to return the first one. Here is the postcondition:
h
m
k
Post R :
v
b
>v
≥v
We can get an invariant by replacing k by a fresh variable i :
h
m
i
k
inv P :
v
?
b
>v
≥v
How does it start? At the beginning, the smallest value found so far is in
b[h] . So we set both i and m to h.
When is it done? The invariant and postcondition look the same when i=k .
How does it make progress? Increment i to make unknown section smaller.
/** = index of minimum value o f b[h..k]. Precondition: h≤k */
public static int min( int [] b, int h, int k) {
int m= h; int i= h;
// {inv: b[m] is the minimum of b[h..i]}
while (i != k) {
i= i + 1;
if (b[i] < b[m])
{ m= i; }
}
return m;
}
Figure 8.6:
Function min
Search WWH ::

Custom Search