CODEWITHSUNDEEP
pythonpython-3.x
JoeSchmoe
JoeSchmoe

Reputation: 21

How to find the index at which a new item would be inserted in a sorted list?

given a list of words :

fruits = ['Abiu','Açaí','Acerola','Ackee','Bilberry','Blackberry','Blackcurrant','Black sapote','Blueberry','Boysenberry','Breadfruit','Magellan Barberry','Mamey Apple','Mamey','Sapote','Mango']

i wanted to get the 3 words less and greater than a given word : e.g.

key= 'Banana'

in this case Banana will come after 'Ackee' ad before 'Bilberry' if sorted lexically.

the end result would be a list like this:

['Açaí','Acerola','Ackee','Bilberry','Blackberry','Blackcurrant']

i have something like this and it works but I would like to know if there is a faster way to do it:

 words_before  = [fruit for fruit in fruits if fruit.lower() <= key]
 words_after = [fruit for fruit in fruits if fruit.lower() >= key]

 new_list = words_before[len(words_before)-3:len(words_before)] + words_after[0:3]

Upvotes: 2

Views: 100

Answers (1)

Mark
Mark

Reputation: 92461

When you are looking to quickly find the insertion point in a sorted list, you should reach for the built in bisect module:

from bisect import bisect

fruits = ['Abiu','Açaí','Acerola','Ackee','Bilberry','Blackberry','Blackcurrant','Black sapote','Blueberry','Boysenberry','Breadfruit','Magellan Barberry','Mamey Apple','Mamey','Sapote','Mango']
key= 'Banana'

i = bisect(fruits, key)
fruits[i - 3: i] + fruits[i: i + 3]

# ['Açaí', 'Acerola', 'Ackee', 'Bilberry', 'Blackberry', 'Blackcurrant']

Here i will be the place in the list to insert key. Given that, you can take a slice in both directions.

Upvotes: 2

Related Questions