Prologue:
Let L be a list of integers.
Let L[p : q] be an nonempty slice, i.e., 0 ≤ p < q ≤ len(L).
We say that L[p : q] is unimodal iff there is a natural number m such that
(a) p≤m<q;
(b) L[p : m + 1] strictly increasing;
(c) L[m : q] is strictly decreasing.
Furthermore, such a number m, if it exists, is call the mode of L[p : q].
Since L is the same as L[0 : len(L)], we also say that L is unimodal if L[0 : len(L)] is unimodal.
Algorithm:
def Mode(A,p,q):
if p+1==q:
return A[p]
else:
m=⌊p+q⌋ 2
ifA[m−1]<A[m]:
return Mode(A,m,q)
else:
return Mode(A,p,m)
Proof of Correctness:
Let P(n) denote the assertion that if A is a list of integers, 0 ≤ p < q ≤ len(A), A[p : q] is unimodal, and n = q − p, then M ax(A, p, q) terminates and returns the maximum element of A[p : q].
Note that we are using q − p (length of the slice being considered) as size of input.
We prove that for all integers n ∈ N, n ≥ 1, P (n) holds.
Base Case: Let n = 1. Then q − p = 1, or equivalently, p + 1 = q. Thus A[p : q] is a slice of one element, and A[p] is its maximum element.
By Line 2, A[p] is returned as wanted.
Induction Step: Let n ∈ N,n > 1. 318
Suppose for all j ∈ N, 1 ≤ j < n,P(j) holds. [IH]
WTP: P(n) holds.
Since q − p = n > 1, Lines 4-8 run. There are two cases to consider.
Case 1: A[m − 1] < A[m].
Then by Line 6, Max(A,m,q) is called and returned.
By Line 4 and Hint 2, p < m < q, and so 1 ≤ q − m < q − p.
By the IH, M ax(A, m, q) terminates and returns the maximum element of A[m : q].
Since A[m − 1] < A[m], the mode of A[p : q] must equal the mode of A[m : q].
So the maximum element of A[p : q] equals the maximum element of A[m : q]. Therefore M ax(A, p, q) terminates and returns the maximum element of A[p : q], as wanted.
Case 2: A[m − 1] > A[m]:
Similar to Case 1; left as an exercise. 433