CMPT 120: Lab 10

Write a function isSorted that takes a list as its argument and returns True if the list is in sorted (increasing) order. You function should do this without sorting.

Hint: look at ajacent pairs of values (like the repeated letters with sorting did), and watch for values that are out of order.

>>> isSorted([1, 2, 5, 7, 100, 10000])
True

>>> isSorted([10000, 100, 7, 5, 2, 1])
False

>>> isSorted([1, 5, 2, 7, 100, 10000])
False

---

The search algorithms we have seen only return one of the positions of a value in the list. It's possible that a particular value will occur multiple times. In some cases, you want all of the occurrences returned.

Write a function multiSearch that takes a list and value as its argument. It should return a list of all positions in the list where the value occurs. If the value doesn't occur, this will be the empty list.

>>> testlist = [5, 2, 9, 8, 9, 2, 6, 0, 9, 1]
>>> multiSearch(testlist, 9)
[2, 4, 8]

>>> multiSearch(testlist, 4)
[]

>>> multiSearch(testlist, 0)
[7]

You may find it useful to start with the implementation of linear search from the Guide. You can modify this to build (and then return) a list of the relevant positions.

---

Write a function median that takes a list of numbers as its argument and returns the list's median.

The median is the value in the list that has an equal number of values that are larger and smaller. If the list has an even length, the median is the average of the two middle elements.

>>> print median( [32,10,54,23,21] )
23

>>> print median( [42,13,80,85,22,43] )
42.5

Hint: sort the list first.