Question

Assume that you are using linear search algorithm to find the position of element x=9 in the list L={1,2,3,4,5,6,7,8,9,10}. What is the number of comparisons done by the algorithm until it finds the position of x? (Include all comparisons in your count!)

Linear search algorithm is given as:
procedure linear search(x:integer, a1, a2, …,an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location

Answer 1

Sure, I can help you with that!

Since we are searching for the element x=9 in the list L={1,2,3,4,5,6,7,8,9,10} using linear search, we start by comparing x with the first element of the list which is 1. Since x ≠ 1, we move to the next element and compare x with 2. This process continues until we reach the element x=9.

Therefore, the number of comparisons done by the algorithm until it finds the position of x=9 is 9 (comparing x with 1, 2, 3, 4, 5, 6, 7, 8, and finally 9).