分治法计算最大值和最小值

爱疯

'http://baike.baidu.com/item/分治算法
'http://blog.sina.com.cn/s/blog_6d53ced50102va6b.html
Sub test()
    Dim A()
    A = Array(-13, 13, 9, -5, 7, 23, 0, 15)
    MsgBox "min=" & f(A, LBound(A), UBound(A))
End Sub

'求最小值
Function f(A(), i As Integer, j As Integer)
    Dim mid As Integer, temp1, temp2
    If i = j Then
        '1个元素
        f = A(i)
    ElseIf j - 1 = i Then
        '2个元素
        f = IIf(A(i) < A(j), A(i), A(j))
    Else
        '多于2个元素
        mid = (i + j) / 2
        temp1 = f(A, i, mid)
        temp2 = f(A, mid + 1, j)
        f = IIf(temp1 < temp2, temp1, temp2)
    End If
End Function

爱疯

Sub test()
    Dim A(), min, max
    A = Array(3, 4, 2, 6, 8, 1, 9, 12, 15, 11)
    Call minmax(A, LBound(A), UBound(A), min, max)
    Debug.Print "max=" & max
    Debug.Print "min=" & min
End Sub


Sub minmax(A(), i As Integer, j As Integer, min, max)
    Dim lmin, lmax, rmin, rmax, mid As Integer
    If i = j Then
        '1个元素
        min = A(i)
        max = A(i)
    ElseIf j - 1 = i Then
        '2个元素
        If A(i) > A(j) Then
            min = A(j)
            max = A(i)
        Else
            min = A(i)
            max = A(j)
        End If
    Else
        '多于2个元素
        mid = (i + j) / 2
        Call minmax(A, i, mid, lmin, lmax)      '求i~mid之间的最大最小值分别为lmax，lmin
        Call minmax(A, mid + 1, j, rmin, rmax)  '求mid+1~j之间的最大最小值分别为rmax，rmin
        min = IIf(lmin > rmin, rmin, lmin)      '比较lmin和rmin，小的就是最小值
        max = IIf(lmax > rmax, lmax, rmax)      '比较lmax和rmax，大的就是最大值
    End If
End Sub




'https://stackoverflow.com/questions/13544476/how-to-find-max-and-min-in-array-using-minimum-comparisons
让我意外的是：
1）min、max：保存当前区域的最小值和最大值。
2）lmin（或rmin）对应min，lmax（或rmax）对应max。递归结束后，才产生值。
3）结果开始保存在min、max，接着保存在lmin（或rmin）、lmax（或rmax）。... 随着递归都结束后，最终保存在min、max。