英文:
How to use binary search on an existing SortedList with a key function?
问题
我想在具有键函数的 SortedList 上使用二分查找，例如类似于 bisect 模块中的 bisect_right()。然而，SortedList.bisect_right() 仅支持按值搜索。如何使其与键函数配合工作？
英文:
I would like to use binary search on a SortedList with a key function, e.g. similarly to bisect_right() in the bisect module. However, SortedList.bisect_right() only supports searching by value. How to make it work with a key function?
答案1
得分: 0
你可以在 SortedList 的构造函数中指定 key。
https://grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList
SortedList 根据该键进行排序，而 SortedList 中的 bisect 方法必须使用相同的键，因为二分法需要了解列表的排序方式。
英文:
You specify the key for a SortedList in its constructor.
https://grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList
The SortedList is sorted according to that key, and the bisect methods in SortedList necessarily use the same key, since bisection requires an understanding of how the list is sorted.
答案2
得分: 0
如果您已经有一个按给定键排序的SortedList，可以在其上使用bisect.bisect_right，例如：
bisect.bisect_right(sorted_list, value, key=keyfunc)
如果您需要重复搜索，更高效的方法是创建一个SortedKeyList 并使用其bisect_key_right() 方法。额外的效率来自于在二进制搜索期间不索引排序列表，因为这本身是一个O(log(n)) 操作。
英文:
If you have a SortedList already and it's sorted by the given key, you can use bisect.bisect_right on that, e.g.:
bisect.bisect_right(sorted_list, value, key=keyfunc)
If you need to search repeatedly, it would be more efficient to create a SortedKeyList and use its bisect_key_right() method. The extra efficiency comes from not indexing the sorted list during a binary search, as that itself is a O(log(n)) operation.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论