时间戳

首页 > 解决方案 > 使用二分查找和用户输入

python - 使用二分查找和用户输入

问题描述

我试图弄清楚如何在已经排序的列表上使用二进制搜索，这样我就可以让用户搜索用户输入的名称，并让它显示名称（如果存在）或告诉用户它是否存在不是。

我不能使用内置的排序功能。

我有气泡搜索设置来对用户输入的名称列表进行排序，代码如下：

def names():
  members = []
  done = False
  while done != True:
    mem = input("Enter a name, enter 'done' when finished: ")
    if mem == "done":
      done = True
    else:
      members.append(mem)
    print(members)

    index = len(members) - 1
    sort = False

    while not sort:
        sort = True
        for j in range(0, index):
            if members[j] > members[j + 1]:
                sort = False
                members[j], members[j + 1] = members[j + 1], members[j]


#Here is the output for the first code:

Enter a name, enter 'done' when finished: Bob
['Bob']
Enter a name, enter 'done' when finished: George
['Bob', 'George']
Enter a name, enter 'done' when finished: Mike
['Bob', 'George', 'Mike']
Enter a name, enter 'done' when finished: Zed
['Bob', 'George', 'Mike', 'Zed']
Enter a name, enter 'done' when finished: Vorp
['Bob', 'George', 'Mike', 'Zed', 'Vorp']
Enter a name, enter 'done' when finished: done
['Bob', 'George', 'Mike', 'Vorp', 'Zed']

我创建了另一个用于搜索排序列表的函数，这就是我卡住的地方。我试图获取排序列表并将其放在我的main()函数中，但它没有打印任何内容。

def main(members):
    name_search = input("Please enter the name you're looking for: ")
    print(name_search)
    begin_index = 0
    end_index = len(members) -1
    
    while begin_index <= end_index:
        midpoint = begin_index + (end_index - begin_index) // 2
        midpoint_value = members[midpoint]
        if midpoint_value == members:
            return midpoint
        elif members < midpoint_value:
            end_index = midpoint - 1

        else:
            begin_index = midpoint + 1
    print(members)

    return None
names()

有人介意帮忙吗？

标签： pythonbinary-search

解决方案

它与常规二进制搜索的算法基本相同，只需将数字列表替换为名称列表：

def binary(lst, sml, bg, x): 
    if bg >= sml: 
        mid = (bg + sml) // 2
        if lst[mid] == x: 
            return mid 
        elif lst[mid] > x: 
            return binary(lst, sml, mid - 1, x) 
        else: 
            return binary(lst, mid + 1, bg, x) 
    else: 
        return -1
  
lst = ['Bob', 'George', 'Mike', 'Vorp', 'Zed'] 
x = input('Input the name: ')

index = binary(lst, 0, len(lst)-1, x) 
  
if index != -1: 
    print(index) 
else: 
    print("Not in list.")

输入：

Input the name: Mike

输出：

2

推荐阅读