Finding the insertion point in a list

[Steven D'Aprano]

On Fri, 16 Mar 2007 18:17:08 -0800, Paul Rubin wrote:

> tkpmep at hotmail.com writes:
>> Or with a generator comprehension
>> n  = sum ( y>x[i] for i in range(len(x)) ) - 1
>> 
>> But there  has to be a cleaner way, as the first approach is unwieldy
>> and does not adapt to changing list lengths, and the second is not
>> obvious to a casual reader of the code.
> 
> How about:
> 
>   n = len([y > t for t in x])

(1) It's wrong. That always returns the length of the list. Perhaps you
meant something like this?

len(["anything will do" for t in x if y > t])

or even

len(filter(lambda t, y=y: y>t, x))



(2) It's barely more comprehensible than the alternative that the Original
Poster rejected for being insufficiently clear.

Since (almost) everyone insists on ignoring the bisect module and
re-inventing the wheel, here's my wheel:


def find(alist, n):
    """Return the position where n should be inserted in a sorted list."""
    if alist != sorted(alist):
        raise ValueError('list must be sorted')
    where = None
    for i in range(len(alist)):
        if where is not None:
            break
        alist.insert(i, n)
        if alist == sorted(alist):
            where = i
        del alist[i]
    if where is None:
        where = len(alist)
    return where


Here's another dodgy implementation:


def find(alist, n):
    return sorted(alist + [n]).index(n)

It's especially good for large lists. Not!



-- 
Steven.