Question

The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. Specify the steps of this algorithm.

Short answer

The ternary search algorithm is given as:

\user1 procedure ternary search ( $x_1,x_2,....,x_n$integers with $n\ge 1,a$integer)

$$\begin{gathered} v:=1 \\ y:=m \end{gathered}$$

\user1while$v<y-1$

Algorithm will return$location$ , which is the position of searched element in the list.

Step-by-step solution

Algorithm

Algorithm for Binary Search:

\user1procedurebinary search ( a : integer,$x_1,x_2,..,x_n:increa\sin g$ )

$i:=1${i is left endpoint of search interval}

$j:=n$ { j is right endpoint of search interval}

\user1while$i<j$

convert binary search to ternary search

Make changes in,

\user1while$i<j$

First change is divide using 3 instead of dividing by 2 .

The algorithm based on above conditions given as:

\user1 procedure ternary search ( $x_1,x_2,...,x_n$integers with $n\ge 1,a:$integer)

$$\begin{gathered} v:=1 \\ y:=m \end{gathered}$$

\user1while$v<y-1$