在Python中实现跳转搜索的结果不正确

2024-03-29 09:49:10 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试用Python实现跳转搜索。代码在我看来逻辑上很好。除了数组的第一个元素,我得到了所有数字的-1。有人能帮忙吗?你知道吗

def jumpsearch(array,x):
    n=len(array)
    m=int(sqrt(n))

    if array[0]>x:
        return -1

    for i in (0,n-1,m):
        if array[i]==x:
            return i
        if x<array[i]:
            for k in (i-m,i):
                if array[k]==x:
                    return k           
    return -1            

j=[1,2,3,4,5,6,7,8]
print(j)
jumpsearch(j,2) 

Tags: 代码in元素forlenreturnifdef
1条回答
网友
1楼 · 发布于 2024-03-29 09:49:10

执行for k in (i-m,i):时,不会在某个范围内迭代,但k只取2个值:i-1m。你知道吗

for i in (0,n,m):行相同。你知道吗

你也会得到不正确的结果,因为你从来没有检查在最后一块。实际上,即使执行for i in range(0, n, m):,当i+m>;=n时也会停止,因此必须检查最后一部分以确保元素不在那里。你知道吗

def jumpsearch(array, x):
    n=len(array)
    m=int(math.sqrt(n))

    if array[0] > x:
        return -1

    for i in range(0, n, m):        
        if array[i] == x:
            return i
        elif x < array[i]:
            for k in range(i-m, i):
                if array[k]==x:
                    return k 
            else:
                return -1  
    for j in range(i+1,n):
        if array[j] == x:
            return j
    else:
        return -1

相关问题 更多 >