Finding the insertion point in a list

[kyosohma at gmail.com]

On Mar 16, 12:59 pm, tkp... at hotmail.com wrote:
> I have an ordered list e.g. x = [0, 100, 200, 1000], and given any
> positive integer y, I want to determine its appropriate position in
> the list (i.e the point at which I would have to insert it in order to
> keep the list sorted. I can clearly do this with a series of if
> statements:
>
> if y<x[1]:
>     n = 0
> elif y < x[2]:
>     n = 1
> elif y < x[3]:
>     n = 2
> else:
>     n = 3
>
> 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.
>
> My list will typically have 2 to 5 items, so speed is not a huge
> issue. I'd appreciate your guidance.
>
> Sincerely
>
> Thomas Philips

One way to do this would be to use the cmp built-in and loop over the
items in the list. Maybe something like this:

x = [0, 100, 200, 1000]
numLst = len(x)
count = 0
for i in range(numLst):
	resultOfCmp = cmp(newNum, x[count])
	if resultOfCmp == -1:
		print i
		x.insert(count, newNum)
		break
	count += 1

# Where newNum is the one to be inserted.

It's a hack, but it might get the ol' creative juices flowing.

Mike