2
A=[2,3,5,7,11,13]
print(A.index(5))

The answer is 2, But what I need is the first one which is bigger than 4 (the answer will be the same - 2). I can apply a while loop, but is there a more elegant or a builtin way to do it? In my problem the list is sorted in an ascending order (no duplication), and my target is to split it into two lists: lower or equal to 4, and bigger than 4; and given the list is sorted it would be redundant to scan it twice (or even once).

Geri Reshef
  • 397
  • 1
  • 6
  • 17

4 Answers4

5

As @DanD.mentioned, you can use the bisect module for this, in you example you can use bisect_left

>>> import bisect
>>> bisect.bisect_left(A, 5)
2

This will use a binary search since your data is sorted, which will be faster than a linear search (O(logN) instead of O(N)).

If you want the index of the first value greater than 4, then you can switch to bisect_right

>>> bisect.bisect_right(A, 4)
2
Cory Kramer
  • 114,268
  • 16
  • 167
  • 218
  • For splitting the list into "lower or equal" and "bigger", on the other hand, `bisect_right` should be used. – tobias_k Feb 19 '18 at 12:22
3

You're totally correct about efficiency - if you have already sorted list, do not iterate linearly, its waste of time

There's built-in bisect module - exactly for binary search in sorted containers.

You're probably looking for bisect_right function.

Slam
  • 8,112
  • 1
  • 36
  • 44
1

Thanks everybody, the answer using your kind help is:

import bisect
A=[2,3,5,7,11,13]
N=bisect.bisect_right(A,4)
print(A[:N]) #[2,3]
print(A[N:]) #[5,7,11,13]
Geri Reshef
  • 397
  • 1
  • 6
  • 17
0

Use next with a default argument:

val = next((i for i, x in enumerate(A) if x > 4), len(A))

Given the above result, you can then do:

left, right = A[:val], A[val:]
Ma0
  • 15,057
  • 4
  • 35
  • 65
  • Is `False` a good default here? When not explicitly checked with `is`, it will be interpreted as `0`. IMHO better use `-1` (also has to be checked, but more standard), `None`, or just no default. – tobias_k Feb 19 '18 at 12:37
  • @tobias_k It might be not intuitive **but** `[2, 3, 4][False:]` returns `[2, 3, 4]` which is what you want to have. That would not happen with `-1` (`[4]`). `0` would also work just fine. – Ma0 Feb 19 '18 at 12:39
  • Actually, no, because `A[False:]` should return the elements that are _larger_ than `4`, i.e. `[]` in your example. So, for the slicing case _only_, `len(A)` would be a better default. – tobias_k Feb 19 '18 at 12:43
  • @tobias_k Oh, yeah. Thanks for noticing. Then how about `len(A)` as a default? – Ma0 Feb 19 '18 at 12:45