如何在fi创建的列表上实现二进制搜索

Question

这是我的第一篇帖子，请温柔一点。我正在整理一些 文件按升序和降序排列。一旦我对一个文件进行了排序，我就把它存储在一个分配给变量的列表中。然后用户选择一个文件并搜索一个项目。我收到一条错误消息。。。。你知道吗

TypeError: unorderable types; int() < list()

……当我尝试使用排序列表的变量搜索项目时，错误出现在代码的第27行。通过研究，我知道int和list是无法比较的，但我一辈子都想不出如何在一个大的（600）列表中搜索一个项目。 目前我只是在玩二进制搜索来适应它。 如有任何建议，将不胜感激。你知道吗

year = []
    with open("Year_1.txt") as file:
        for line in file:
            line = line.strip()
            year.append(line)

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    while first<=last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
        found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
    return found

selectionSort(year)
testlist = []
testlist.append(year)
print(binarySearch(testlist, 2014))

1.txt文件由600项组成，所有年份的格式均为2016年。 它们按降序排列，从2017年开始，一直到2013年。希望这有道理。你知道吗

Answer 1

你不使用Python: bisect模块有什么原因吗？你知道吗

比如：

import bisect

sorted_year = list()
for each in year:
    bisect.insort(sorted_year, each)

。。。足以创建排序列表。然后可以使用文档中的函数来搜索它。你知道吗

（实际上，您可以使用year.sort()对列表进行适当排序。。。bisect.insort()在从输入流构建列表而不是调用year.append()时可能会稍微有效一些。。。但是我关于使用`对分模块的观点仍然存在）。你知道吗

还要注意，600项对于现代计算平台来说是微不足道的。即使是6000也只需要几毫秒。在我的笔记本电脑上，对60万个随机整数进行排序大约需要180毫秒，而类似大小的字符串仍然需要不到200毫秒

因此，在这个应用程序中，以这种数据规模对这个列表进行排序，可能不会得到任何结果。你知道吗

另一方面，Python的标准库中还包含许多模块，用于管理结构化数据和数据文件。例如，可以使用Python: SQLite3。你知道吗

使用它，您可以使用标准的sqlddl（数据定义语言）来描述您的数据结构和模式，sqldml（数据操作语言：INSERT、UPDATE和DELETE语句）来管理数据的内容，并使用SQL查询从中获取数据。使用标准的SQL ORDER BY子句，可以按任意列以及任意数量的列的升序和降序混合返回数据，并且可以向架构中添加索引，以确保数据的存储方式能够在您选择的任何键上以任何顺序进行高效的查询和遍历（表扫描）。你知道吗

因为Python在其标准库中包含SQLite，而且SQLite在简单的本地文件上提供SQL客户机/服务器语义。。。在结构化数据中使用它几乎没有坏处。你不需要安装和维护额外的软件、服务器、处理到远程数据库服务器的网络连接等等。你知道吗

Answer 2

在得到答案之前，我要走几步。你知道吗

你需要发布一个[mcve]。与其告诉我们从“Year1.txt”中读取我们没有的内容，不如将列表本身放入代码中。您需要600个条目才能得到代码中的错误吗？不，这就足够了：

year = ["2001", "2002", "2003"]

如果你真的需要600个条目，那么就提供它们。发布实际数据，或者

year = [str(x) for x in range(2017-600, 2017)]

你发布的代码需要被剪切，粘贴，砰-在我的电脑上复制错误就这样。你知道吗

selectionSort与问题完全无关，因此请将其从问题中完全删除。事实上，既然你说输入已经排序了，我也不确定selectionSort在你的代码中到底应该做什么。：）

接下来您说testlist=[].append（year）。在这里询问之前使用调试器。只需查看变量中的值，问题就显而易见了。你知道吗

How to append list to second list (concatenate lists)

修复这意味着您现在有一个要搜索的内容列表。在你搜索一个列表，看看2014年是否符合其中的一件事，那就是所有年份的完整列表。你知道吗

现在我们进入二进制搜索。如果你看变量，你会发现你在比较整数2014和一些字符串，可能是“1716”，如果它允许你这么做的话，答案是没有用的（我有Python2.7，所以我不确定你到底得到了什么）。但关键是在字符串列表中找不到整数2014，因此它总是返回False。你知道吗

如果没有调试器，那么可以放置策略性的print语句，如

print ("debug info: binarySearch comparing ", item, alist[midpoint])

现在，在我修复了其他问题之后，VBB在评论中所说的对我有用。如果你正在寻找一些甚至不在列表中的东西，并且期望是真的，那就错了。如果您提供了要搜索的正确列表，则搜索“2014”返回True。或者，您可以强制它使用字符串，然后搜索它。您可以在输入阶段强制所有年份为int。但int 2014与字符串“2014”不同。你知道吗