StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q13E

Expert-verifiedFound in: Page 202

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 using

a) A linear search. **b) **A binary search.

_{ }This type of algorithm is also known as Sequential Search because it follows a particular path in a pre-defined sequence, whenever it is executed.

A linear search algorithm starts by comparing two variables, that is x and a_{1. }If x = a_{1}, it implies that outcome is the location of a_{1. }Only iff, if x ≠ a_{1, }then next search should be executed, which is, if x = a_{2, }it implies that outcome is the location of a_{2.}

This process of sequential search continues to execute until a match of the required result is found.

According to given question,

The sequence is 1, 3, 4, 5, 6, 8, 9, 11 and we need to search for the element 9.

Comparing x = a_{1 }⇒ 9 = a_{1}

Substituting a_{1} = 1.

1 does not match 9

Comparing x = a_{2 }⇒ 9 = a_{2}

Substituting a_{2} = 3.

3 does not match 9

Comparing x = a_{3 }⇒ 9 = a_{3}

Substituting a_{3} = 4

4 does not match 9

Comparing x = a_{4 }⇒ 9 = a_{4}

Substituting a_{4} = 1.

5 does not match 9

Comparing x = a_{5 }⇒ 9 = a_{5}

Substituting a_{5} = 6

6 does not match 9

Comparing x = a_{6 }⇒ 9 = a_{6}

Substituting a_{6} = 8.

8 does not match 9

Comparing x = a_{7 }⇒ 9 = a_{7}

Substituting a_{7} = 9.

9 matches with 9

Therefore, by linear search 9 is contained at the 7^{th }element in the sequence.

A binary search algorithm is when the searching list of elements has monotonically increasing terms. Its mechanism works by comparing the element which is to be locates to the middle term of the list while breaking or splitting the list into further small smaller sub lists of the same size. This process continues by bringing down the sub list based on the comparison of the elements which is to be located.

According to the question,

The given sequence is 1, 3, 4, 5, 6, 8, 9, and 11

Split the sequence in half. 1,3,4,5 and 6, 8, 9, 11

5 is the maximum of the sequence of 1, 3, 4, 5

5 is less than 7.

Thus, 7 is not in the sequence 1,3,4,5. Therefore, discarding the sequence 1,3,4,5.

Split the sequence 6, 8,9,11 in half. 6, 8 and 9, 11

It is clear that 8 is the maximum of the sequence amongst 6,8 and 7 is less than 8

Thus 7 is not in the sequence 6,8. Therefore discarding the sequence 6,8

Split the sequence 9, 11 in half . 9 and 11

9 is the maximum of the sequence 9 and it is not greater than 9

Thus 9 is not in the sequence of 11.

We have sequence 9 remaining.

Since, 9 is equal to 9, location of 9 is determined in the sequence as 7^{th} element.

Therefore, the obtained 9 is the 7^{th }element of the sequence 1,3,4,5,6,8,9,11.

94% of StudySmarter users get better grades.

Sign up for free