Question

Recall the linear search algorithm:

procedure linear search (x: integer, a1, a2, ..., an: distinct integers)

i := 1

while (i ≤ n and x 6= ai) i := i + 1 if i ≤ n then location:= i else location:= 0 return location

Apply the linear search algorithm to search for the number 3 in the list 1, 5, 3, 9.

(a) In this application of the algorithm, what is the integer n?

(b) What is the initial value of i?

(c) How many iterations of the while loop occur when applied to this list?

(d) What is the value of i after the while loop finishes its iterations?

(e) What does the algorithm return?

Answer 1

(a) In this application of the algorithm, what is the integer n?

>> n is the number of items in the list. So, n = 4(as per the list 1,5,3,9)

(b) What is the initial value of i?

>> 1

(c) How many iterations of the while loop occur when applied to this list?

>> 3

(d) What is the value of i after the while loop finishes its iterations?

>> 3

(e) What does the algorithm return?

>> location=3

Linear search is a sequential search. It will search through every element in the list.

For the list 1, 5, 3, 9,

n=4

i=1

x is the item being searched. So, here, x = 3

tracing while loop:

i=1	i<=4, True	x=ai? => x = a1 ? => x = 1 ? => 3 = 1 ? False	i=i+1=2
i=2	i<=4, True	=> x = a2 ? => x = 5 ? => 3 = 5 ? False	i=i+1=3
i=3	i<=4, True	=> x = a3 ? => x = 3 ? => 3 = 3 ? True	-

At this stage the number is found, so i = 3. So, here i<=n which is 3<=4? True and hence it will return location as i which is 3. So, the location returned is 3 which seems to be true as 3 is in 3rd position in the list 1, 5, 3, 9.