题目

Problem

Use the binary search algorithm to try to locate the word “Parallelogram” in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.

Arc, Centre, Chord, Circle, Circumference, Diameter, Radius, Sector, Segment, Tangent

(Total 4 marks)

题目中文翻译

使用二分搜索算法尝试在以下字母列表中定位单词”Parallelogram”。清楚说明如何选择枢轴以及每个阶段拒绝列表的哪一部分。

Arc、Centre、Chord、Circle、Circumference、Diameter、Radius、Sector、Segment、Tangent

解答

解法一

思路

展开

为列表中的单词编号 $1$ 至 $10$ ，每次使用 middle-right 位置作为枢轴。把目标单词与枢轴按字母顺序比较后，连同枢轴一起排除不可能包含目标的那一半；继续到候选区间为空为止。

答题过程

展开

Number the words from $1$ to $10$ . The first middle-right pivot is

\left\lceil\frac{1+10}{2}\right\rceil=6,

which is Diameter. Since Parallelogram comes after Diameter alphabetically, reject positions $1$ to $6$ and retain positions $7$ to $10$ .

The next pivot is

\left\lceil\frac{7+10}{2}\right\rceil=9,

which is Segment. Since Parallelogram comes before Segment, reject positions $9$ and $10$ and retain positions $7$ and $8$ .

The next pivot is

\left\lceil\frac{7+8}{2}\right\rceil=8,

which is Sector. Since Parallelogram comes before Sector, reject position $8$ .

The only remaining word, at position $7$ , is Radius. This is not Parallelogram, so position $7$ is also rejected.

Therefore

\boxed{\text{Parallelogram is not in the list.}}

IAL 2021 Jan D1 Q1

题目

解答

解法一

思路

答题过程