二进制搜索的基本特征

Question

a = [ (123, "cat", "meow", 1.4, 125),
      (245, "dog", "bark", 8.9, 100),
      (573, "cow", "moo", 3.50, 59)]

大家好，我第一次学代码。上面是一个列表的例子。如果我想让用户在列表里面输入任何东西，比如573.系统就会用二进制搜索在列表中搜索573，并显示出与573相关的任何东西，也就是（573，"狗"，"叫"，8.9，100）。我真的需要你的帮助。非常感谢 如果我说的有什么不清楚的地方，欢迎评论。

Answer 1

解决办法

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid][0]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

a = [ (123, "cat", "meow", 1.4, 125),
      (245, "dog", "bark", 8.9, 100),
      (573, "cow", "moo", 3.50, 59),
      (873, "cow", "moo", 3.50, 59)]

ans = binary_search(a, 573)
if ans >= 0:
   print(a[ans])
else:
   print("not Found")

产量

它返回元素在列表中的位置。

(573, "cow", "moo", 3.50, 59)

Answer 2

我想你的输出应该是元组吗，如果没有找到键，也许是空的。

def findKey(alist,k):
    n=len(alist)
    if(alist[n//2][0] != k):
        if(n==1):
            pass
        elif(alist[n//2][0] < k):
            return findKey(alist[n//2+1:],k)
        else:
            return findKey(alist[:n//2],k)
    else:
        return alist[n//2]


a = [ (123, "cat", "meow", 1.4, 125),
      (245, "dog", "bark", 8.9, 100),
      (573, "cow", "moo", 3.50, 59),
      (579, "cow", "moo", 3.50, 59)]

print(findKey(a,573))