时间戳

首页 > 解决方案 > Python散列二分搜索

python - Python散列二分搜索

问题描述

编写一个 binary_search 函数，该函数在每一步都打印正在搜索的列表，如下面的输出所示。它显示了当前正在搜索的子列表以及如何将其拆分为围绕中点的两部分。

这是我尝试过的，但仍然很难找到解决方案：

def binary_search(a_list, item):
    print(a_list)  # just to show the search area
    if a_list == []:
        return False
    midpoint = len(a_list) // 2
    element = a_list[midpoint]
    if item == element:
        return True
    elif item < element:  # first half
        return binary_search(a_list[:midpoint], item)
    else:
        return binary_search(a_list[midpoint + 1:], item)

给定输入：

test_list = [0,1,2,8,13,17,19,32,42]
binary_search(test_list,3)
binary_search(test_list,13)

预期输出：

[0, 1, 2, 8, 13, 17, 19, 32, 42]
[0, 1, 2, 8] 13 [17, 19, 32, 42]
[0, 1, 2, 8]
[0, 1] 2 [8]
[8]
[] 8 []
[]
[0, 1, 2, 8, 13, 17, 19, 32, 42]
[0, 1, 2, 8] 13 [17, 19, 32, 42]

标签： python

解决方案

您需要将列表打印到元素的左侧和右侧，试一试：

def binary_search(a_list, item):
    print(a_list) 
    if a_list == []:
        return False
    midpoint = len(a_list) // 2
    element = a_list[midpoint]
    left = a_list[:midpoint]
    right = a_list[midpoint+1:]
    print(left,element,right )

    if item == element:
        return True
    elif item < element: # first half
        return binary_search(left, item)
    else:
        return binary_search(right, item)

输入：

test_list = [0,1,2,8,13,17,19,32,42]
binary_search(test_list,3)

输出：

[0, 1, 2, 8, 13, 17, 19, 32, 42]
[0, 1, 2, 8] 13 [17, 19, 32, 42]
[0, 1, 2, 8]
[0, 1] 2 [8]
[8]
[] 8 []
[]

推荐阅读