Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
411 views
in Technique[技术] by (71.8m points)

python - Given boundaries, find interval

Having a list like this

[207, 357, 470, 497, 537]

where each number denotes the boundary of an interval (0 being implicit at the beginning of the list), what is a pythonic way of finding out to which interval a given number n belongs to?

So the intervals are

0: (0, 207)
1: (208, 357)
2: (358, 497)
3: (498, 537)

If n=0, then the corresponding interval is 0, for n=360, it's 2.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Using the bisect module of course:

>>> import bisect
>>> lst = [207, 357, 470, 497, 537]
>>> bisect.bisect_left(lst, 0)
0
>>> bisect.bisect_left(lst, 360)
2

The module uses binary search, which requires a sorted sequence. With such a sequence you can divide the sequence in half by picking an index mid-way between the first and last, to see if the value you need is in either half. You then continue dividing the selected half until you found a matching insertion point. That lets you find the insertion point in O(log N) time for a sequence of length N, i.e. very fast.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...