上面列表中的数字是十个箱子的重量（单位：千克）。箱子将用容器运输，每个容器最多可容纳 40 千克。

$17 \quad 9 \quad 15 \quad 8 \quad 20 \quad 13 \quad 28 \quad 4 \quad 12 \quad 5$

(a) 计算运输箱子所需容器数量的下界。必须展示计算过程。

(b) 使用首次适应装箱算法将箱子分配给容器。

(c) 使用提供的列表，执行快速排序以产生升序的重量列表。必须清楚标出枢轴。

(d) 使用二分搜索算法尝试在排序列表中定位重量 9。清楚说明如何选择枢轴以及每个阶段拒绝列表的哪一部分。

先求十个箱子的总重量，再除以每个容器的容量 40。所得结果必须向上取整，因为不足一个完整容器的余量仍需另用一个容器。

The total weight is

Hence

Therefore the lower bound is

按原顺序逐个处理重量。每次都从 Container 1 开始，放入第一个尚有足够剩余容量的容器；只有现有容器都放不下时才开启新容器。

Applying first-fit in the given order gives:

Thus the first-fit allocation is

采用 middle-right 规则选择枢轴。每次把小于枢轴的数放在左侧，大于枢轴的数放在右侧，再对尚未排好的子列表重复。下列竖线表示枢轴已经固定在最终位置。

Using middle-right pivots:

Initial pivot: $13$.

Next pivots: $4$ and $20$.

Next pivots: $12$ and $15$.

Next pivot: $8$.

也可始终采用 middle-left 规则。只要每个子列表都一致地使用这一规则，并正确完成每次划分，就会得到相同的升序列表。

Using middle-left pivots:

Initial pivot: $20$.

Next pivot: $8$.

Next pivots: $4$ and $15$.

Next pivot: $13$.

Finally use pivot $9$ on the remaining sublist $9,12$:

在升序列表中使用 middle-right 元素作枢轴。将目标值 9 与枢轴比较，每次排除不可能含有 9 的一半，直至找到 9。

The sorted list is

For positions $1$ to $10$, the middle-right position is $6$, so the pivot is $13$. Since $9<13$, reject $13$ to $28$.

For positions $1$ to $5$, the middle-right position is $3$, so the pivot is $8$. Since $9>8$, reject $4$ to $8$.

For positions $4$ to $5$, the middle-right position is $5$, so the pivot is $12$. Since $9<12$, reject $12$.

The only remaining value is at position $4$: