题目中提到了折半查找（二分查找），查找平均长度为 2.2。

题目给出的 S 的序列顺序满足字典序，有 do<for<repeat<while ，由于所有元素首字母互不相同，绘图时用一个元素的首字母代表该元素。

字典序：基于字母顺序排列的单词按字母顺序排列的方法，一般英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。英文中的字母按照ASCII码表顺序排序，即 a<b<c<d<e<f<g<h<i<j<k<l<m<n<o<p<q<r<s<t<u<v<w<x<y<z ，

例如 a<bd<c 。如果一个字符串是另一个字符串的前缀，短的字符串排在前面，例如 a<aa<aaa 。

C++中对字符串数组的排序默认是按照字典序进行排序。

下面进行验证。

采用闭区间（也可采用半开区间或开区间）折半向下取整模板，对应的二叉搜索树（折半查找判定树）如图(a)所示：

#include <iostream>
#include <vector>
using namespace std;

int SL(vector<string>& S, string target){
    int left = 0, right = (int)S.size() - 1;
    int len = 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if (S[mid] == target) {
            return len;
        } else if(S[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        len++;
    }
    return 0;
}

int main() {
    vector<string> S = {"do", "for", "repeat", "while"};
    vector<float> P = {0.35, 0.15, 0.15, 0.35};
    float ans = SL(S, S[0]) * P[0] + SL(S, S[1]) * P[1] + SL(S, S[2]) * P[2] + SL(S, S[3]) * P[3];
    cout << ans;
    return 0;
}

采用闭区间（也可采用半开区间或开区间）折半向上取整模板，对应的二叉搜索树（折半查找判定树）如图(b)所示：

#include <iostream>
#include <vector>
using namespace std;

int SL(vector<string>& S, string target){
    int left = 0, right = (int)S.size() - 1;
    int len = 1;
    while(left <= right) {
        int mid = (left + right + 1) / 2;
        if (S[mid] == target) {
            return len;
        } else if(S[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        len++;
    }
    return 0;
}

int main() {
    vector<string> S = {"do", "for", "repeat", "while"};
    vector<float> P = {0.35, 0.15, 0.15, 0.35};
    float ans = SL(S, S[0]) * P[0] + SL(S, S[1]) * P[1] + SL(S, S[2]) * P[2] + SL(S, S[3]) * P[3];
    cout << ans;
    return 0;
}

结果均为2.2，符合要求。

定义一个结点的深度(depth)为从根结点到该结点的简单路径中的结点个数，对于关键字 ki 所在结点，记其深度为 depth(ki) 。

定义查找长度(search length)为查找目标元素所需的比较次数，对于关键字 ki ，记其查找长度为 SL(ki) 。

一个关键字的查找长度等于其对应二叉搜索树中所在结点色深度，即 depth(ki)=SL(ki) 。

若已知目标元素所在位置靠近序列头部，则采用顺序查找，有时候比折半查找更快。

⑴ 采用顺序存储结构进行顺序查找，明显查找概率高的优先级高，所以元素应该按照查找概率从高到低排序。

如图(c)所示，若查找概率相同，排列顺序随机。

ASL成功=0.35×1+0.35×2+0.15×3+0.15×4=2.1

⑵ 采用链式存储结构进行顺序查找，明显查找概率高的优先级高，所以元素应该按照查找概率从高到低排序。

如图(d)所示，若查找概率相同，排列顺序随机。

ASL成功=0.35×1+0.35×2+0.15×3+0.15×4=2.1

也可以用二叉链表构造一棵最优二叉搜索树。

最优二叉搜索树(optimal binary search tree)：给定一个由 n 个互不相同的关键字组成的序列K=⟨k1,k2,…,kn⟩，其中 k1<k2<⋯<kn，用这些关键字构造一棵二叉搜索树。对于每个关键字 ki，查找其的的概率为 pi，可能有些被查找的关键字不在 K 中，我们需要构造 n+1 个虚关键字 d0,d1,d2,…,dn，其中d0<k1，dn>kn，ki<di<ki+1，其中i=1,2,…,n−1，对于每个关键字 di，查找其的的概率为qi。每个关键字ki对应二叉搜索树中一个内部结点，每个虚关键字di对应二叉搜索树中一个叶结点，这样每次查找关键字如果查找成功，那么最终落在ki，如果查找失败，那么最终落在di。

给定一棵二叉搜索树T，假定一次搜索代价为访问的结点数，那么在T中进行一次搜索期望的代价为：

其中 depth(ki) 表示 ki 所在结点的深度，等于根结点到 ki 所在结点的路径上结点个数。对于一个给定的概率集合，我们希望构造一棵期望搜索代价最小的二叉搜索树，我们称这样一棵二叉搜索树为最优二叉搜索树。

最优二叉搜索树为超纲内容，考场上想不到理论上不会扣分。

本题中，由于  ， 则 中的搜索代价 。

如果要构造一棵最优二叉搜索树 T ，原则上只能采用动态规划方法，但好在题目中的案例过于简单，可以采用贪心策略构造。

不同于前面的顺序表和单链表，二叉搜索树必须要按照一定顺序构造。常用的顺序有字典序和标准序，当然也可以自定义顺序。

首先按照字典序排序 {“do”, “for”, “repeat”, “while”} ，有 do<for<repeat<while ，可构造最优二叉搜索树，如图(e)字典序所示。

ASL成功=0.35×2+0.15×1+0.35×2+0.15×3=2.0

或 ASL成功=0.35×2+0.15×3+0.15×1+0.35×2=2.0