python - 三元搜索不会返回答案

Question

我为递归三元函数编写了以下代码：

def ternary_search(start,stop,x,arr):
    pos1 = start + (stop-start)//3
    pos2 = stop - (stop - start)//3
    
    if (pos1<=pos2):
        val1 = arr[pos1]
        val2 = arr[pos2] 

        if val1 == x:
            print(pos1)
            return pos1
        elif val2 == x:
            print(pos2)
            return pos2

        if x < val1:
            ternary_search(start,pos1-1,x,arr)
        elif x > val2:
            ternary_search(pos2+1,stop,x,arr)    
        else:
            ternary_search(pos1+1,pos2,x,arr)
    else: 
        return -1

即使代码运行良好，我也没有得到返回值。

import numpy as np
a = np.arange(1,100,5) # array([ 1,  6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91, 96])
pos = ternary_search(0,len(a),86,a)
print(pos == None)

输出：

17

True

Answer 1

你应该return在调用函数时添加

if x < val1:
    return ternary_search(start,pos1-1,x,arr)
elif x > val2:
    return ternary_search(pos2+1,stop,x,arr)    
else:
    return ternary_search(pos1+1,pos2,x,arr)