CODEWITHSUNDEEP
python-2.7python-3.x
Apollo
Apollo

Reputation: 9064

Inclusive range of list Python

I'm trying to find the minimum elements within a section of a list. In the following example, a is the start and b is the end. I would like these indexes to partition the list inclusively, so that if the list is [1,2,3,9,4,10] the indexes 1 to 4 would include 2 and 4.

def minimum (a,b,list):
    return min(list[a:b])

In other words, is there a way to make list[a:b] inclusive?

Upvotes: 4

Views: 12168

Answers (1)

Brian Schmitz
Brian Schmitz

Reputation: 1043

By default, no.

For this case, it is more conventional to do:

min(li[a:b + 1])

Also beware of naming your variable list, as it can have unintended consequences (silent namespace issues), as "list" also names the built-in list container type.

If you simply want to write your own minimum method, you can encapsulate this behavior in your minimum method using the above method so you don't have to think about it ever again.

Side note: Standard list-slicing uses O(N) space and can get expensive for large lists if minimum is called over and over gain. A cheaper O(1) space alternative would be:

def minimum(a, b, li):
    min(itertools.islice(li, a, b + 1))

EDIT: Don't use islice unless you are slicing starting at the beginning of the list or have tight memory constraints. It first iterates up to a, rather than directly indexing to a, which can take O(b) run-time.

A better solution would be something like this, which runs with O(b-a) run-time and O(1) space:

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 fancier solution that you can use if the list is static (elements are not deleted and inserted during the series of queries) is to perform Range Minimum Queries using segment trees: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

Building the tree requires O(N) run-time and O(N) space, although all queries after that require only O(log(N)) run-time and O(1) additional space.

Upvotes: 2

Related Questions