Python list inclusive range
I am trying to find the minimum items in a list section. In the following example: a is the start and b is the end. I would like these indices to split the list inclusively, so that if the list is [1,2,3,9,4,10], indices 1 through 4 will include 2 and 4.
def minimum (a,b,list):
return min(list[a:b])
In other words, is there a way to do it list[a:b]
inclusively?
source to share
By default, no.
For this case, more conditionally:
min(li[a:b + 1])
Also beware of naming your variable list, as it can have unintended consequences (quiet namespace problems), since "list" also names the container type of the inline list.
If you just want to write your own minimal method, you can encapsulate this behavior in your minimal method using the above method so that it doesn't occur to you to think about it again.
Side note: standard list overlay uses O (N) space and can get expensive for large lists if the minimum is called over again. A cheaper O (1) alternative would be:
def minimum(a, b, li):
min(itertools.islice(li, a, b + 1))
EDIT: Don't use islice unless you slice starting from the beginning of the list or have limited memory limits. It iterates to a first, not direct indexing to a, which can take O (b) execution time.
A better solution would be something like this, which runs with O (ba) runtime and O (1):
def minimum(li, a=0, b=None):
if b is None:
b = len(li) - 1
if b - a < 0:
raise ValueError("minimum() arg is an empty sequence")
current_min = li[a]
for index in xrange(a, b + 1):
current_min = min(current_min, li[index])
return current_min
A more preferred solution that you can use if the list is static (no items are removed or inserted during a series of queries) is to do Minimum Range Queries using segment trees: http://www.geeksforgeeks.org/segment-tree- set-1-range-minimum-query /
It takes O (N) and O (N) execution times to build the tree, although all queries after that only require O (log (N)) and O (1) extra space.
source to share