在没有内置函数的情况下获取排序列表中的索引位置

Question

我的任务是在列表中找到

x

的索引位置。我已经尝试了很多次，但对于某些值，我似乎总是得到错误的索引位置。规则是：

• 没有内置功能

• 适用于所有可能的 x

• 使用分而治之的方法将列表一分为二，直到获得索引位置

• 列表已排序

我尝试使用 while 循环实现递归函数，但没有一个给我正确的答案。

这是我的代码：

list1=[0,1,2,3,4,5,6,7,8] # change to get other values
x=int(input("Enter a number to get its index position: "))

def find_without_built_in_functions(list1, x, start, end):
    if start<=end and x in list1:
        mid=start+((end-1)//2)
        if x==list1[mid]:
            y=mid
            return y
        elif x<list1[mid]:
            return find_without_built_in_functions(list1, x, start+1, mid)
        elif x>list1[mid]:
            return find_without_built_in_functions(list1, x, mid, end+1)
        return -1
print(find_without_built_in_functions(list1, x, 0, len(list1)-1))

Answer 1

您的代码的问题在于，在 elif 分支中，您没有正确更新 end 和 start 的值。您应该增加开始或减少结束，具体取决于您正在搜索列表的哪一半。

def find_without_built_in_functions(list1, x, start, end):
    if start <= end:
        mid = (start + end) // 2
        if list1[mid] == x:
            return mid
        elif list1[mid] > x:
            return find_without_built_in_functions(list1, x, start, mid - 1)
        else:
            return find_without_built_in_functions(list1, x, mid + 1, end)
    else:
        return -1

Answer 2

1. 将中点计算为两个端点的平均值，向下舍入。

mid = (start + end) // 2

2. 当目标小于中间元素时，搜索空间应该缩小到

   [start, mid)

   .

return find_without_built_in_functions(list1, x, start, mid - 1)

3. 当目标大于中间元素时，搜索空间应该缩小到

   (mid, end]

   .

return find_without_built_in_functions(list1, x, mid + 1, end)

4. return -1

   应该在

   if

   块之外，以便在元素不存在时返回

   -1

   而不是

   None

   。