3. List all the steps used to search for 9 in the sequence 1, 3, 4, 5, 6, 8, 9, 11 usinga) a linear search b) a binary search.

a) Linear Search:

1. Start at the first element of the sequence.
2. Compare the first element (1) with the target value (9). They are not equal.
3. Move to the next element (3) and compare it with the target value (9). They are not equal.
4. Move to the next element (4) and compare it with the target value (9). They are not equal.
5. Move to the next element (5) and compare it with the target value (9). They are not equal.
6. Move to the next element (6) and compare it with the target value (9). They are not equal.
7. Move to the next element (8) and compare it with the target value (9). They are not equal.
8. Move to the next element (9) and compare it with the target value (9). They are equal.
9. The target value (9) is found at the 7th position in the sequence.

b) Binary Search:

1. Start with the entire sequence: 1, 3, 4, 5, 6, 8, 9, 11.
2. Find the middle element. The middle index is (0+7)/2 = 3.5, rounded down to 3. The middle element is 5.
3. Compare the middle element (5) with the target value (9). Since 9 is greater than 5, focus on the right half of the sequence: 6, 8, 9, 11.
4. Find the middle element of the right half. The new middle index is (4+7)/2 = 5.5, rounded down to 5. The middle element is 8.
5. Compare the middle element (8) with the target value (9). Since 9 is greater than 8, focus on the right half of the new sequence: 9, 11.
6. Find the middle element of the new right half. The new middle index is (6+7)/2 = 6.5, rounded down to 6. The middle element is 9.
7. Compare the middle element (9) with the target value (9). They are equal.
8. The target value (9) is found at the 7th position in the sequence.