algorithm - Recursive algorithm to find the smallest element

Question

I want to write a recursive algorithm to find a smallest element. I draw a binary tree in which leaf represents the elements and internal nodes are smallest elements after comparison.

Input to algo is :

5 3 1 9 8 7 6 10

Binary Tree :

Output : 1

I need to find an algorithm that somehow incorporates this binary tree. First compare pair of elements and than reduced the problem to n/2 then n/4 .. and when n become 1 we get the answer.

Answer 1

使用分而治之。

让M(i, j)表示“子数组”的最小元素[i...j]。然后M(i, j) = min(M(i, k), M(k + 1, j))，如果i < j（我留给你找出合适的k）。

此外，您需要处理好案件i = j。

Answer 2

这是一个在树中找到最小值的函数：

function smallest(tree)
    if isEmpty(tree)
        return infinity
    return min( tree.value,
                smallest(tree.leftKid),
                smallest(tree.rightKid) )

但我不明白你的问题。如果输入是数组的形式，则不需要构建树。只需遍历数组，成对比较值，在每一步保持最小值，并在最后输出最小值。

Answer 3

伪代码：

mydata = [5 3 1 9 8 7 6 10];
n = 8;
while n > 1
  for ii = 2 to n Step 2
    mydata[ii/2]=min(mydata[ii-1],mydata[ii]);
  next ii
  n = n/2;
wend