给定一个无序序列，编程实现平均查找长度最小的二叉排序树的构造，并编写二叉排序树查找函数。

要构造一个平均查找长度最小的二叉排序树，可以使用动态规划的方法。具体步骤如下：

1. **定义子问题**：设`dp[i][j]`表示从序列的第`i`个元素到第`j`个元素构造的二叉排序树的最小平均查找长度。
2. **状态转移方程**：对于每个子问题`dp[i][j]`，我们选择一个根节点`k`，然后将序列分成两部分，左子树和右子树。状态转移方程为：
\[
dp[i][j] = \min_{i \leq k \leq j} \left( \sum_{m=i}^{j} f(m, k) + dp[i][k-1] + dp[k+1][j] \right)
\]
其中，`f(m, k)`表示节点`m`到根节点`k`的深度。
3. **边界条件**：当`i > j`时，`dp[i][j] = 0`。

下面是具体的实现代码：

def optimal_bst(keys, freq):
    n = len(keys)
    dp = [[0] * (n+1) for _ in range(n+1)]
    
    for i in range(n):
        dp[i][i] = freq[i]
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            total_freq = sum(freq[m] for m in range(i, j+1))
            
            for k in range(i, j+1):
                left = dp[i][k-1] if k > i else 0
                right = dp[k+1][j] if k < j else 0
                dp[i][j] = min(dp[i][j], left + right + total_freq)
    
    return dp[0][n-1]

def build_bst(keys, freq):
    n = len(keys)
    dp = [[0] * (n+1) for _ in range(n+1)]
    root = [[0] * (n+1) for _ in range(n+1)]
    
    for i in range(n):
        dp[i][i] = freq[i]
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            total_freq = sum(freq[m] for m in range(i, j+1))
            
            for k in range(i, j+1):
                left = dp[i][k-1] if k > i else 0
                right = dp[k+1][j] if k < j else 0
                if left + right + total_freq < dp[i][j]:
                    dp[i][j] = left + right + total_freq
                    root[i][j] = k
    
    return root

def construct_bst(keys, root, i, j):
    if i > j:
        return None
    if i == j:
        return TreeNode(keys[i])
    
    k = root[i][j]
    node = TreeNode(keys[k])
    node.left = construct_bst(keys, root, i, k-1)
    node.right = construct_bst(keys, root, k+1, j)
    
    return node

def search_bst(node, key):
    if node is None:
        return False
    if key == node.val:
        return True
    elif key < node.val:
        return search_bst(node.left, key)
    else:
        return search_bst(node.right, key)

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 示例使用
keys = [10, 12, 20, 30, 25]
freq = [34, 8, 50, 10, 25]
root = build_bst(keys, freq)
bst_root = construct_bst(keys, root, 0, len(keys)-1)
print(search_bst(bst_root, 25))  # 输出: True