python - 为什么python的bisect_left即使值不存在也返回有效索引?
问题描述
我想查找排序数组中是否存在数字。直截了当,数组包含从 1 到 63 的斐波那契数。下面是斐波那契数生成器及其一些输出。
stacksize = 10000 # default 128 stack
from functools import lru_cache
@lru_cache(stacksize)
def nthfibonacci(n):
if n <= 1:
return 1
elif n == 2:
return 1
elif n > 2:
return nthfibonacci(n - 2) + nthfibonacci(n - 1)
output = [nthfibonacci(k) for k in range(1,63+1)]
# truncated output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,987,
1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,.....]
现在我想查找数字 7是否存在所以我使用以下代码使用 python bisection 模块
from bisect import bisect_left
elem_index = bisect_left(a=output, x=7, lo=0, hi=len(arr) - 1)
# output of elem_index is 5 ???? . But it is expected to be len(output) +1, right?
# as we know if element is not found it returns len(array) +1
同样,如果我只是编写一个简单的二进制搜索,它会给我正确的结果,如下所示:
def binsearch(arr, key):
# arr.sort()
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
else:
if arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
print(binsearch(arr, 7)) # it gives me -1 as expected
那么发生了什么?
解决方案
如前所述,bisect_left()
只需在列表中定位元素的插入点即可保持排序顺序。该文档还显示了如何将bisect_*
函数转换为实际查找,因此您可以使用:
def index(lst, elem):
i = bisect_left(lst, elem)
if i != len(lst) and lst[i] == elem:
return i
return -1
推荐阅读
- python-3.x - 错误:使用 sudo pip3.8 install websocket 命令出错,退出状态为 1,
- python - 更改 for 循环的上一个条目
- visual-studio-code - 在 Visual Studio Code 上集成 ZSH 时出现字体问题
- python - 有没有办法从 python 请求中捕获 InsecureRequestWarning
- xamarin - 在 Xamarin iOS 中的应用程序之间切换时 Web 服务请求卡住
- flutter - Dart & Flutter:如何将抽象类的实现传递给另一个类的构造函数?
- javascript - 单击下划线后使用jquery更改类名
- csv - 读取 CSV 以解析数据并将其存储在 Hash 中
- javascript - 根据 ECMAScript,带有参数的函数调用是否有效的左侧表达式
- sql - MVC(实体框架)将 ID 更改从“创建视图”保存到 SQL 数据库表