Python 3

Write a function findmin that takes such a list as an argument and returns the minimum element (return the element, not its index). It should use binary search. Assume that the items in the list repeat at most k times where k is assumed to be a constant (in the analysis) and is given as a parameter to findmin . Your function should run in O(log n)time.

Above, you assumed the items repeated at most a constant number of times.Now, you will write some functions that will find how many times a given item repeats. You can do this with binary search and it will take O(log n) time. A better goal would be to find the repeats in O(log(r)) where is the number of repeats of the target item. This can be done with a variant of binary search called doubling search. In doubling search, we start at one index and then we look at one step forward, then two steps forward, then four steps, then 8, then 16, etc. Once we have gone too far, we do a binary search on the subset of the list between where we started and where we went to far. First, write two functions firstrepeat and lastrepeat that each take two arguments, a list L and an index i . The firstrepeat function should return the smallest index j such that L[i] ==L[j] . Similarly, the lastrepeat function should return the largest index j such that L[i] == L[j] .