0

我想使用python植入递归搜索，它将为给定的键
示例划分上半部分：list[2, 4, 6, 9, 10]
for the key is 6 case, return index is 3
for the key is 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)


例如 list [2, 4, 6, 9, 10] 和 key 为 7
代码不能终止


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

4

1 回答 1

0 
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
于 2020-02-10T20:31:48.587 回答