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

ajsxfq5m 于 2023-03-30 发布在 PyCharm

关注(0)|答案(2)|浏览(154)

我被赋予了一个任务，要在列表中找到x的索引位置。我已经尝试了很多次，但我似乎总是得到一些值的错误索引位置。规则是：

无内置函数
对所有可能的x有效
使用divide and conquer将列表一分为二，直到获得索引位置
列表已排序

我尝试使用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))

pycharm

来源：https://stackoverflow.com/questions/75861983/getting-an-index-position-in-a-sorted-list-without-built-in-functions

2条答案

按热度按时间

mftmpeh81#

你的代码的问题是，在elif分支中，你没有正确地更新end和start的值。你应该增加start或减少end，这取决于你正在搜索列表的哪一半。

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

赞(0）回复(0）举报 2023-03-30

p1iqtdky2#

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

mid = (start + end) // 2

1.当目标小于中间元素时，搜索空间应该缩小到[start, mid)。

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

1.当目标大于中间元素时，搜索空间应缩小到(mid, end]。

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

return -1应该在if块之外，以便当元素不存在时返回-1而不是None。

赞(0）回复(0）举报 2023-03-30

我来回答

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

2条答案

相关问题

热门标签

最新问答