Deadline: Tu 4/7/2015 at 7 AM
Refer to the Week 12 reading or other resources as necessary to complete this assignment.
This lab is all about different ways of answering one question: If I have a list L and a value v, how can I determine whether v is an element of L, and if so, what its index is?
For example, if I have the list ['A', 'B', 'C'] and the value 'C', my answer would be that 'C' is at position 2 in the list.
The functionss we write will return None if the value is not in the list. So if I search the same list for 'D', the answer would be None. Note that None (no quotes!!) is a built-in Python constant just like True and False.
Answer Question 1 in your pre-lab.
If the list is not guaranteed to be in any particular order, we can't do any better than looping through it, looking at each element, and seeing if that element is equal to our desired value.
For example, if we have the list ['A', 'B', 'C'], and we're looking for 'B', we would start by comparing 'B' to 'A'. In the next iteration of the loop, we would compare 'B' to 'B' and return a 1.
However, if we were searching for 'D' instead, we would have to look at every element of the list before reaching the conclusion that 'D' is not present.
Answer Question 2 in your pre-lab.
If the list is guaranteed to be in sorted order, we can actually do better than examining every single element. Here's how:
If we have the list ['A', 'B', 'C'], and we're looking for 'C', and we know that the list is in alphabetical order, we can start by comparing 'C' to the middle element. Since 'C' comes after the middle element alphabetically, we can rule out the element in position 0 without even looking at it. For a longer list, we can keep repeating this trick to cut the list in half, and then half again, and so on.
Answer Question 3 in your pre-lab.
Review your answers, and then click the Next button at the bottom of the Moodle quiz.
Once you do that, you should see something similar to this:
Click the Submit all and finish button. You MUST do this so that your
pre-lab can be graded! Once you have submitted your quiz, you should see
something similar to this at the top of your Moodle window. The important part is that the State shows up as Finished.
