使用默认参数的递归二进制搜索 - Python

Question

我正在尝试在 Python 中编写一个二进制搜索函数，该函数最初从用户那里获取两个参数：要搜索的值 i 和一个排序数组 arr。由于它不会总是运行在数组的同一部分，它还需要两个额外的参数，一个上限 u 和一个下限 l；因为我希望初始调用只接受两个参数，所以我想将 0 设置为下限的默认值（在递归调用中显然不会这样，其中 idx 是下限bound if idx < i) 和数组的长度作为上限（我不认为我需要加 1 因为它总是等于最高索引加 1 但如果我错了请纠正我） .

我遇到的问题是我不知道如何将长度作为参数传递。这是我的定义：

def binSearch(arr, i, l=0, u=len(arr)):
    lower = l
    upper = u
    idx = (lower+upper)//2
    print("Lower bound: " + lower + '\n' + "Upper bound: " + upper + '\n' + "Average: " + idx + '\n')

（当然不是实际功能，只是初步调试）

这是我运行时收到的错误消息：

Traceback (most recent call last):
  File "/Users/mac/Desktop/programming/python/binarysearch.py", line 1, in <module>
    def binSearch(arr, i, l=0, u=len(arr)):
NameError: name 'arr' is not defined

显然我无法在参数中的参数名称上调用函数，但我想不出另一种可能的方法来将“我将要使用的数组的长度”翻译成 Python.有帮助吗？

Answer 1

将默认设置为 None，如果 u 为 None，则将 upper 设置为 len(arr)

def binSearch(arr, i, l=0, u=None):
    lower = l
    if u is not None: # You could do 'if u' if you're sure u is never 0.
        upper = u
    else:
        upper = len(arr)
    idx = (lower+upper)//2
    print("Lower bound: " + lower + '\n' + "Upper bound: " + upper + '\n' + "Average: " + idx

稍作清理：

def binSearch(arr, i, lower=0, upper=None):
    if upper is None:
        upper = len(arr)
    idx = (lower+upper)//2
    print("Lower bound: " + lower + '\n' + "Upper bound: " + upper + '\n' + "Average: " + idx

使用默认参数的递归二进制搜索 - Python

Recursive binary search with default arguments - Python

python

arrays

arguments

function

python-3.x