Python首选项查找器如何实现二进制插入

Question

我正在创建一个程序，它接受一个文件，每行有一个新的“东西”。为了测试，我使用了NBA篮球队（共有30支球队）。 它会询问A和B的人，直到它可以创建一个他们最喜欢到最不喜欢的“东西”的完整列表。你知道吗

到目前为止，这是一个魅力，但提出了太多的问题。我已经阅读并理解了一个关于二进制插入排序的答案，可以在这里找到：https://stackoverflow.com/a/33748286/8419835 但是，我在实现它时遇到了问题，我目前的代码结构是如何的。你知道吗

options = []
toPrint = []
with open("list.txt", "r") as f:
    for line in f.read().splitlines():
        options.append(dict(name=line,superiors=[],inferiors=[],active=False))

print()
for o in options:
    o['active'] = True
    for c in options:
        if c != o and c['active'] and o['name'] not in c['superiors'] and o['name'] not in c['inferiors'] and c['name'] not in o['superiors'] and c['name'] not in o['inferiors']:
            choice = input(o['name'] + ' (1) or ' + c['name'] + ' (2) ? : ')
            if choice == '2':
                c['inferiors'].append(o['name'])
                c['inferiors'].extend(o['inferiors'])
                o['superiors'].append(c['name'])
                o['superiors'].extend(c['superiors'])
                c['inferiors'] = list(set(c['inferiors']))
                o['superiors'] = list(set(o['superiors']))
            else:
                o['inferiors'].append(c['name'])
                o['inferiors'].extend(c['inferiors'])
                c['superiors'].append(o['name'])
                c['superiors'].extend(o['superiors'])
                o['inferiors'] = list(set(o['inferiors']))
                c['superiors'] = list(set(c['superiors']))

print()
for x in range(30):
    for o in options:
        if len(o['superiors']) == x:
            toPrint.append(o['name'])
for x in range(30):
    print(str(x + 1) + '. ' + toPrint[x])
print()

有没有人对我如何使用我目前拥有的代码有任何想法，并对其进行修改，以使其提出尽可能少的问题，如上面的链接所示？你知道吗

Answer 1

举个例子： 我们将在{a，B，C，D，E，F}中排名
我们可以用一个集装箱连续装运最终订单。
初始容器=[] 现在我们将遍历给定的列表：

1. First iteration for A,container=[], as container is empty we can easily store A. After iteration container =[A]

2. Second iteration for B,container=[A], we can insert B by asking only one question. After iteration container =[A,B] or [B,A]

3. During third iteration, we can ask two questions to find c's position and insert C

4. During fourth iteration, we can ask 3 questions and insert D

5. During fifth iteration, we can ask 4 questions and insert E

6. During nth iteration, we can ask n-1 questions and insert nth element in its

因此，我们需要O（n*（n-1））次查询或请求在它们之间排序。
但是我们可以使用二进制搜索将这个数字减少到O（n*（logn））。
每次搜索元素位置时，我们都可以使用二进制搜索来查找其位置，因为如果A>；B和B>；C，那么A>；C

代码：

options = []
toPrint = []
with open("list.txt", "r") as f:
    for line in f.read().splitlines():
        options.append(line)

print()

curren_list=[]
cnt=0
for o in range(0,len(options)):
    lo=0
    hi=len(curren_list)-1
    index=0

    while lo<=hi:
        mid=int((lo+hi)/2)
        choice = input(curren_list[mid] + ' (1) or ' + options[o] + ' (2) ? : ')
        cnt=cnt+1
        if choice=='1':
            lo=mid+1
            index=mid+1
        else:
            hi=mid-1

    curren_list=curren_list[0:index]+[options[o]]+curren_list[index:len(curren_list)]

print("Number of asking: ",cnt)
print()
for x in range(len(curren_list)):
    print(str(x + 1) + '. ' + curren_list[x])
print()