Chapter 15 Worksheet

Answer the following, assuming a program uses the linear search:

1. If a list has n elements, in the best case how many elements
would the computer need to check before it found the desired element?

2. If a list has n elements, in the worst case how many elements
would the computer need to check before it found the desired element?

3. If a list has n elements, how many elements need to be checked to
determine that the desired element does not exist in the list?

4. If a list has n elements, what would the average number of
elements be that the computer would need to check before it found the desired
element?

5. (2 pts) Take the example linear search code and put it in a function called
linear_search. Take in the list along with the desired element as
parameters. Return the position of the element, or -1 if it was not found.
Remember, RETURN the value. If your function has a print statement in it, you
are doing it wrong.
Once you've written the function, try it out with the following code to see if
it works:

# --- Put your definition for linear_search right below:

# --- Now if the function works, all these tests should pass:

my_list = [4, 3, 2, 1, 5, 7, 6]

r = linear_search(my_list, 3)
if r == 1:
print("Test A passed")
else:
print("Test A failed. Expected 1 and got", r)

r = linear_search(my_list, 2)
if r == 2:
print("Test B passed")
else:
print("Test B failed. Expected 2 and got", r)

r = linear_search(my_list, 10)
if r == -1:
print("Test C passed")
else:
print("Test C failed. Expected -1 and got", r)

Answer the following, assuming a program uses the binary search, and the
search list is in order:

6. If a list has n elements, in the best case how many
elements would the computer need to check before it found the desired element?

7. If a list has n elements, in the worst case how many
elements would the computer need to check before it found the desired element?

8. If a list has n elements, how many elements need to be checked to
determine that the desired element does not exist in the list?

9. If a list has n elements, what would the
average number of elements be that the computer would need to check
before it found the desired element?

10. (2 pts.) Take the example binary search code and put it in a function
named binary_search. Take in the list along with the desired
element as parameters. Return the position of the element, or -1 if it
was not found. Once you've written the function, try it out with the
following code to see if it works:

# --- Put your definition for binary_search right below:

# --- Now if the function works, all these tests should pass:

my_list = [0, 3, 5, 12, 18, 50, 70, 78]

r = binary_search(my_list, 3)
if r == 1:
print("Test A passed")
else:
print("Test A failed. Expected 1 and got", r)

r = binary_search(my_list, 5)
if r == 2:
print("Test B passed")
else:
print("Test B failed. Expected 2 and got", r)

r = binary_search(my_list, 10)
if r == -1:
print("Test C passed")
else:
print("Test C failed. Expected -1 and got", r)

11. (3 pts.) Does the following function correctly detect whether a list contains
at least one positive element? (1 pt.) Write code to try it out. Explain why it does work
or why it does not work. (1 pt.) Come up with working code. (1 pt.)

def detect_positive(list):
for element in list:
if element > 0:
return True
else:
return False


﻿