Python中的二进制搜索(二等分) [英] Binary search (bisection) in Python

问题描述

是否有一个库函数对列表/元组执行二进制搜索，如果找到则返回项目的位置，否则返回'False'(-1，None等)?

Is there a library function that performs binary search on a list/tuple and return the position of the item if found and 'False' (-1, None, etc.) if not?

我在 bisect模块中找到了bisect_left/right函数，但是它们仍然返回即使项目不在列表中也可以保留位置.完全适合他们的预期用途，但是我只想知道列表中是否有项目(不想插入任何内容).

I found the functions bisect_left/right in the bisect module, but they still return a position even if the item is not in the list. That's perfectly fine for their intended usage, but I just want to know if an item is in the list or not (don't want to insert anything).

我考虑过使用bisect_left，然后检查该位置处的项目是否等于我要搜索的项目，但这似乎很麻烦(而且我还需要进行边界检查，以检查数字是否可以大于最大的数目.我的清单中的数字).如果有更好的方法，我想知道.

I thought of using bisect_left and then checking if the item at that position is equal to what I'm searching, but that seems cumbersome (and I also need to do bounds checking if the number can be larger than the largest number in my list). If there is a nicer method I'd like to know about it.

编辑:明确我的要求:我知道字典非常适​​合此操作，但是我试图将内存消耗保持在尽可能低的水平.我的预期用途是一种双向查询表.我在表中有一个值列表，我需要能够根据它们的索引访问值.而且我还希望能够找到特定值的索引，或者如果该值不在列表中，则查找无".

Edit To clarify what I need this for: I'm aware that a dictionary would be very well suited for this, but I'm trying to keep the memory consumption as low as possible. My intended usage would be a sort of double-way look-up table. I have in the table a list of values and I need to be able to access the values based on their index. And also I want to be able to find the index of a particular value or None if the value is not in the list.

为此使用字典是最快的方法，但会(大约)使内存需求加倍.

Using a dictionary for this would be the fastest way, but would (approximately) double the memory requirements.

我问这个问题的原因是我可能忽略了Python库中的某些内容.看来我必须编写自己的代码，如Moe建议的那样.

I was asking this question thinking that I may have overlooked something in the Python libraries. It seems I'll have to write my own code, as Moe suggested.

推荐答案

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

这篇关于Python中的二进制搜索(二等分)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！