• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q13E

Expert-verified
Found in: Page 202

Discrete Mathematics and its Applications

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 a1. If x = a1, it implies that outcome is the location of a1. Only iff, if x ≠ a1, then next search should be executed, which is, if x = a2, it implies that outcome is the location of a2.

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.

See the step by step solution

Step 1

Comparing x = a1 ⇒ 9 = a1

Step 2

Substituting a1 = 1.

Step 3

1 does not match 9

Step 4

Comparing x = a2 ⇒ 9 = a2

Step 5

Substituting a2 = 3.

Step 6

3 does not match 9

Step 7

Comparing x = a3 ⇒ 9 = a3

Step 8

Substituting a3 = 4

Step 9

4 does not match 9

Step 10

Comparing x = a4 ⇒ 9 = a4

Step 11

Substituting a4 = 1.

Step 12

5 does not match 9

Step 13

Comparing x = a5 ⇒ 9 = a5

Step 14

Substituting a5 = 6

Step 15

6 does not match 9

Step 16

Comparing x = a6 ⇒ 9 = a6

Step 17

Substituting a6 = 8.

Step 18

8 does not match 9

Step 19

Comparing x = a7 ⇒ 9 = a7

Step 20

Substituting a7 = 9.

Step 21

9 matches with 9

Therefore, by linear search 9 is contained at the 7th 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

Step 23

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

Step 24

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

Step 25

5 is less than 7.

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

Step 26

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

Step 27

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

Step 28

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

Step 29

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

Step30

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

Step 31

Thus 9 is not in the sequence of 11.

Step 32

We have sequence 9 remaining.

Step 33

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

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

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.