对给定键的上部进行分区

Question

我想使用 python 植入递归搜索，它将为给定键划分上部
示例：列表[2， 4， 6， 9， 10]
对于键为 6 的情况，返回索引为 3
对于键为 4 的情况，返回索引为 2
如果键不在列表中，即键为 7。它仍然需要返回索引 3，因为 9 大于 7。
如果键不在数组中，我的代码有问题要做递归，
即使我设置了边界条件，我认为这没问题，它无法通过。任何建议都非常感谢。

def qReturn(alist, start, end, key):
if key is 1:
return 0
mid = (start + end)//2
if alist[mid] < key:
return qReturn(alist, mid + 1, end, key)
elif alist[mid] > key:
return qReturn(alist, start, mid, key)
if (start == end | end == mid | start > mid):
return mid+1 
else:
return mid+1

alist = input('Enter the sorted list of numbers: ')
alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))
index = qReturn(alist, 0, len(alist), key)
print('number q is at %d.' %index) 

例如列表 [2， 4， 6， 9， 10]，键为 7
代码无法终止

我需要设置什么样的边界条件并获得 7 的上分区结果？

Answer 1

import numpy as np
alist = np.array([2, 4, 6, 9, 10])
key = 7
#index = qReturn(alist, 0, len(alist), key)
index_bin = (alist>key).argmax(axis=0).T
index_bin

输出：

3

递归的：

def splitAndCheck(leftside, rightside  ):
if (rightside - leftside  <= 0):
if (aList[rightside] >= key):
return rightside
else:
return leftside
middle = (leftside+rightside) //2
if (aList[middle] >= key ):
return splitAndCheck(leftside,middle)
else:
return splitAndCheck(middle+1,rightside)
print(aList) 
for key in range(20):
print('key : ',key,'index : ',splitAndCheck(0,len(aList)-1))

输出：

[ 2  4  6  9 10 12 14 18]
key :  0 index :  0
key :  1 index :  0
key :  2 index :  0
key :  3 index :  1
key :  4 index :  1
key :  5 index :  2
key :  6 index :  2
key :  7 index :  3
key :  8 index :  3
key :  9 index :  3
key :  10 index :  4
key :  11 index :  5
key :  12 index :  5
key :  13 index :  6
key :  14 index :  6
key :  15 index :  7
key :  16 index :  7
key :  17 index :  7
key :  18 index :  7
key :  19 index :  7