2

Given a sorted list and a number n, find the index in the list that precedes n in the most efficient (fastest) way.

sorted list example:

x_list = [1, 3.5, 5, 9.2, 20, 50.75]

number n, say n = 7.5

Example answer: the index of the value in the list that precedes n is 2.

This is what i have tried so far:

x_list = [1, 3.5, 5, 9.2, 20, 50.75]

n = 7.5
for i, v in enumerate(x_list):
    if v < n: xlow = i
    else: break
print(xlow)

Can i do a quicker find than the above method ?

Note: This list is sorted whereas other questions of the same nature are unsorted.

D.L
  • 4,339
  • 5
  • 22
  • 45
  • 1
    [Binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm) – Mechanic Pig Sep 23 '22 at 08:24
  • @MechanicPig, that looks better for large lists. How to implement this ? – D.L Sep 23 '22 at 08:28
  • have a look at [bisect](https://docs.python.org/3/library/bisect.html) module from standard library – buran Sep 23 '22 at 08:29
  • 1
    Does this answer your question? [First Python list index greater than x?](https://stackoverflow.com/questions/2236906/first-python-list-index-greater-than-x) –  Sep 23 '22 at 08:34
  • @KevinChoonLiangYew, this looks great, but is less efficient than bisect from what i can see. – D.L Sep 23 '22 at 08:45
  • 1
    One of the solution in the post is about bisect too, I think you can do a performance check for the top answer and the bisect with large list :D –  Sep 23 '22 at 08:47
  • 1
    @KevinChoonLiangYew Sorting is no mention in that question, so this is not a duplicate. On the contrary, I think this problem is suitable to be a canonical duplicate. – Mechanic Pig Sep 23 '22 at 08:50

1 Answers1

1

You can use bisect to perform a binary search:

import bisect

n = 7.5

index = bisect.bisect_left(x_list, n)-1

output: 2

NB. In case the target is before the first index, this will return -1, which you can avoid using max(0, bisect.bisect_left(x_list, n)-1) if needed.

D.L
  • 4,339
  • 5
  • 22
  • 45
mozway
  • 194,879
  • 13
  • 39
  • 75