[PYTHON] Visualisieren Sie die binäre Suche

import random
import math

def bs_print(elements, low, high, middle):
    """
    visulize binary search process

    """
    es = elements.copy()
    ms = es[middle]
    es.insert(high + 1, ']')
    es.insert(low, '[')
    formatted_elements = " ".join(map(lambda x: str(x), es))
    arrow = [" " * len(str(e)) for e in es]
    arrow[middle+1] = "I".center(len(arrow[middle+1]))
    formatted_arrow = " ".join(arrow)
    print("low: %d, high: %d, middle: %d, x: %d" % (low, high, middle, ms))
    print(formatted_elements)
    print(formatted_arrow)

def bsearch(l, x):
    low = 0
    high = len(l) - 1
    while low <= high:
        middle = math.ceil((low + high) / 2)
        bs_print(l, low, high, middle)
        if l[middle] == x:
            return True
        elif x > l[middle]:
            low = middle + 1
        else:
            high = middle -1
    return False

def random_elements():
    r = [random.choice([i for i in range(20)]) for r in range(41)]
    r.sort()
    return r

if bsearch(random_elements(), 6):
    print("Hit")

Output

low: 0, high: 40, middle: 20, x: 10
[ 0 0 0 1 1 1 2 3 3 3 4 5 6 8 8 8 9 10 10 10 10 10 11 11 12 12 12 12 12 13 13 14 15 15 16 16 16 17 18 19 19 ]
                                             I
low: 0, high: 19, middle: 10, x: 4
[ 0 0 0 1 1 1 2 3 3 3 4 5 6 8 8 8 9 10 10 10 ] 10 10 11 11 12 12 12 12 12 13 13 14 15 15 16 16 16 17 18 19 19
                      I
low: 11, high: 19, middle: 15, x: 8
0 0 0 1 1 1 2 3 3 3 4 [ 5 6 8 8 8 9 10 10 10 ] 10 10 11 11 12 12 12 12 12 13 13 14 15 15 16 16 16 17 18 19 19
                                I
low: 11, high: 14, middle: 13, x: 8
0 0 0 1 1 1 2 3 3 3 4 [ 5 6 8 8 ] 8 9 10 10 10 10 10 11 11 12 12 12 12 12 13 13 14 15 15 16 16 16 17 18 19 19
                            I
low: 11, high: 12, middle: 12, x: 6
0 0 0 1 1 1 2 3 3 3 4 [ 5 6 ] 8 8 8 9 10 10 10 10 10 11 11 12 12 12 12 12 13 13 14 15 15 16 16 16 17 18 19 19
                          I
Hit