python 在排序列表中查找下一个较低的项目

Find next lower item in a sorted list

提问by Sebastian

let's say I have a sorted list of Floats. Now I'd like to get the index of the next lower item of a given value. The usual for-loop aprroach has a complexity of O(n). Since the list is sorted there must be a way to get the index with O(log n).

假设我有一个排序的 Floats 列表。现在我想获取给定值的下一个较低项目的索引。通常的 for 循环 aprroach 的复杂度为 O(n)。由于列表已排序，因此必须有一种方法可以使用 O(log n) 获取索引。

My O(n) approach:

我的 O(n) 方法：

index=0
for i,value in enumerate(mylist):
    if value>compareValue:
        index=i-1

Is there a datatype for solving that problem in O(log n)?

是否有用于解决 O(log n) 中该问题的数据类型？

best regards Sebastian

最好的问候塞巴斯蒂安

回答by stephan

How about bisect?

平分怎么样？

>>> import bisect
>>> float_list = [1.0, 1.3, 2.3, 4.5]
>>> i = bisect.bisect_left(float_list, 2.5)
>>> index = i - 1
>>> index
2

You might have to handle the case of a search value less than or equal to the lowest / leftmost value in the list separately (index == -1in this case).

您可能必须单独处理搜索值小于或等于列表中最低/最左侧值的index == -1情况（在本例中）。

Depending on which index you want to have in case of equality, you might have to use bisect_rightinstead.

根据您希望在相等的情况下使用哪个索引，您可能必须bisect_right改用。

回答by Bart Kiers

You can do a binary search on an array/list to get the index of the object you're looking for and get the index below it to get the lower entry (given that there actually is a lower entry!).

您可以对数组/列表进行二分搜索以获取您要查找的对象的索引并获取其下方的索引以获取较低的条目（假设实际上有较低的条目！）。

See: Binary search (bisection) in Python

请参阅：Python 中的二分搜索（二分法）

Be careful when comparing floating point numbersfor equality!

比较浮点数是否相等时要小心！

回答by miles82

Use the bisectmodule. The function

使用bisect模块。功能

bisect.bisect_left(mylist, compareValue)

returns the proper insertion point for item in list to maintain sorted order.

返回列表中项目的正确插入点以保持排序顺序。

回答by tzot

import bisect

def next_lower_value(values_list, input_value):
    index= bisect.bisect_left(values_list, input_value)
    if index == 0: # there's not a "next lower value"
        raise NotImplementedError # you must decide what to do here
    else:
        return values_list[index - 1]

>>> l= [11, 15, 23, 28, 45, 63, 94]
>>> next_lower_value(l, 64)
63
>>> next_lower_value(l, 63)
45
>>> next_lower_value(l, 1000)
94
>>> next_lower_value(l, 1)
Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    next_lower_value(l, 1)
  File "<pyshell#26>", line 4, in next_lower_value
    raise NotImplementedError # you must decide what to do here
NotImplementedError

Since you request the indexand not the next lower value, change the function next_lower_valueto return index - 1instead of values_list[index - 1].

由于您请求的是索引而不是下一个较低的值，因此将函数更改next_lower_value为 returnindex - 1而不是values_list[index - 1]。

回答by paul

If I'm reading this right, the next lower item is the first item in the list that's less than or equal to x. The bisect documentation for searching sorted listsgives this function:

如果我没看错，下一个较低的项目是列表中小于或等于 x 的第一个项目。用于搜索排序列表的二等分文档提供了此功能：

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

回答by Carl Smotricz

To answer part of the question about datatypes: In a general sense, the datatype most appropriate for finding things in O(log n) time (while maintaining O(1) performance on inserts and deletes!) is the binary tree. You can find things in it by making a series of left-right decisions, which is very analogous to how you do a binary search in a linear list but is (IMO) a little more conceptually intuitive.

回答有关数据类型的部分问题：在一般意义上，最适合在 O(log n) 时间内查找事物的数据类型（同时在插入和删除时保持 O(1) 性能！）是二叉树。您可以通过做出一系列左右决定来找到其中的内容，这与您在线性列表中进行二分搜索的方式非常相似，但 (IMO) 在概念上更直观。

That said, from what little I know of Python, binary trees don't seem to be in the language's standard library. For your application, there would probably be no benefit to include an implementation just for this purpose.

也就是说，根据我对 Python 的了解，二叉树似乎不在该语言的标准库中。对于您的应用程序，仅包含用于此目的的实现可能没有任何好处。

Finally, both binary trees and binary search in a sorted list will allow you to shorten the search by one step: It isn't necessary to search for the key item and then move back to its predecessor. Instead, on every comparison step, if you encounter the key value, act as if it was too large. This will cause your search to end up on the next smaller value. Done carefully, this may also help with the "almost equal floating point value" problem mentioned by bart.

最后，排序列表中的二叉树和二叉搜索都允许您将搜索缩短一步：没有必要搜索关键项然后返回到它的前任。相反，在每个比较步骤中，如果您遇到键值，就好像它太大一样。这将导致您的搜索以下一个较小的值结束。小心完成，这也可能有助于解决 bart 提到的“几乎相等的浮点值”问题。

回答by Naitik Dodia

def lower_bound(arr, x):
    left = 0
    right = len(arr)-1
    mid = -1
    if(arr[left] > x):
        return mid
    while(left <= right):
        mid = int(left + (right - left + 1) / 2)
        if(left == right and right == mid):
            return mid
        if(x > arr[mid]):
            left = mid
        elif(x < arr[mid]):
            right = mid - 1
        else:
            return mid
    return mid

This function returns the index of the element in the sorted list 'arr' if the exact element is found else it returns the index of the largest element smaller than the given number 'x'. If no element is smaller than the given number it returns -1.

如果找到确切的元素，则此函数返回排序列表 'arr' 中元素的索引，否则返回小于给定数字 'x' 的最大元素的索引。如果没有元素小于给定的数字，则返回 -1。