二进制搜索算法 - 项目创意

Question

我正在写一个关于二进制搜索的 python 项目，但我希望能够为这个算法实现一个图形界面。你有什么想法我可以如何使用这个算法来实现接口吗？我的意思是项目想法，而不是实施本身..

谢谢

这是我的代码：

# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1
 
        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1
 
        # means x is present at mid
        else:
            return mid
 
    # If we reach here, then the element was not present
    return -1
 
 
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
# Function call
result = binary_search(arr, x)
 
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")```

Answer 1

虽然您要求图形界面，但仍然只是为了好玩，我决定为您的二进制搜索任务实现以下简单的 ASCII 艺术可视化，它可能对您有用，给您一些想法。

我在将图形绘制到控制台时使用了一些 ANSI escape codes。 Windows 上的这个转义码需要安装一次 colorama 模块 python -m pip install colorama。在 Linux 上它不需要安装任何东西。

代码可以调整为不同的随机种子值或数字数量或数字大小（最多 100，最多 1000，等等）。使用固定种子值随机选择值（在 random.seed(...) 行更改值）。

首先我展示了在我的 Linux (asciinema link) 上录制的 ASCII 视频截屏视频，然后是代码：

代码:

Try it online!

import platform, time, sys
if platform.system() == 'Windows':
    import colorama
    colorama.init()

def vis(data, steps):
    def str_set(s, i, c):
        return s[:i] + c + s[i + 1:]
    def astr_set(a, j, i, c):
        a[j] = str_set(a[j], i, c)
    dlen = max(len(str(e)) for e in data) + 1
    loline = ''.join(str(e).zfill(dlen - 1) + '|' for e in data)
    ll = len(loline)
    N = len(steps)
    h1 = 3
    lines = [' ' * ll for e in range(h1 * N)] + [loline]
    def emit_frame():
        sys.stdout.write("3[F" * len(lines) + '\n'.join(lines) + '\n')
        time.sleep(1)
    emit_frame()
    for i in range(N - 1):
        lpcur, lpnext = [dlen * steps[i + e] + (dlen - 2) // 2 for e in (0, 1)]
        for j in range(h1 - 1):
            astr_set(lines, i * h1 + j, lpcur, '|')
        dir_ = -1 if steps[i + 1] < steps[i] else +1 if steps[i + 1] > steps[i] else 0
        for j in range((i + 1) * h1, len(lines) - 1):
            astr_set(lines, j, lpcur, '.' if j < len(lines) - 2 else '?')
        for j in range(lpcur, lpnext + dir_, dir_):
            astr_set(lines, (i + 1) * h1 - 1, j, ('/' if dir_ < 0 else '\') if j in (lpcur, lpnext) else '-')
            if j == lpcur:
                emit_frame()
        if i == N - 2:
            for j in range((i + 1) * h1, len(lines) - 1):
                astr_set(lines, j, lpnext, '|' if j < len(lines) - 2 else 'V')
            emit_frame()

def binary_search(f, l, r, target):
    steps = []
    while l <= r:
        m = (l + r) // 2
        steps.append(m)
        fm = f(m)
        if fm < target:
            l = m + 1
        elif fm > target:
            r = m - 1
        else:
            break
    return steps

def main():
    import random
    random.seed(3)
    data = sorted(random.randrange(100) for i in range(30))
    target = data[random.randrange(len(data))]
    steps = binary_search(lambda x: data[x], 0, len(data) - 1, target)
    vis(data, steps)

if __name__ == '__main__':
    main()

最终输出：

                                          |                                               
                                          |                                               
                                          \-----------------------\                       
                                          .                       |                       
                                          .                       |                       
                                          .                       \-----------\           
                                          .                       .           |           
                                          .                       .           |           
                                          .                       .     /-----/           
                                          .                       .     |     .           
                                          .                       .     |     .           
                                          .                       .  /--/     .           
                                          .                       .  |  .     .           
                                          .                       .  |  .     .           
                                          ?                       ?  V  ?     ?           
01|08|16|19|19|24|29|29|30|33|47|49|50|60|60|60|60|66|69|69|70|70|74|75|77|77|80|81|81|91|

我还创建了我的代码的略微修改的无限 ASCII 截屏版本（下载代码 here or or Try it online) which produces next fast-playing video (asciinema link）：

还有一个使用 Unicode 字符绘制漂亮的箭头和线条的版本，它还显示了更密集的树，使用更多的数字进行搜索（下载代码 here, or Try it online), you get next video (asciinema link），打开新的下一个视频图像tab/window 的浏览器可以看到它更好更大：

还有一个尝试制作更高级的代码和可视化。现在是两级可视化，前半部分的步骤是垂直绘制的，其余步骤是水平绘制的。这样做是为了获得更高密度的图像，以便在控制台屏幕上显示更多数字。

像往常一样，下载代码here and/or Try it online here. Resulting video is below (plus asciinema link):

Answer 2

您可以为项目使用 django 框架。

在前端提供一个有两个字段的表单

Array itself

The value which you want to search in array

在提交表单时获取值并对输入值应用二进制搜索算法。
在UI

二进制搜索算法 - 项目创意

Binary Search Algorithm - Project Ideas

python

binary-search

python-3.x