优化二进制搜索 [英] Optimize Binary Search

问题描述

我是python的新手，非常热衷于学习算法. 我已经为二进制搜索编写了示例代码，有人可以建议我如何以更多的pythonic方式(优化代码，或者尽可能使用Bisect)获得相同的结果吗?

I am new to python, and very much enthusiastic to learn algorithm. I have written sample code for Binary search, can any one suggest how can i achieve same result in more pythonic way (Optimize the code, or using Bisect if any way possible)?

def bee_search(alist, target):
    sort_list = sorted(alist)

    while len(sort_list) >= 1:
        end = len(sort_list)
        middle = int((0 + end)/2)

        if target == sort_list[middle]:
            print "Found it", str(sort_list[middle])
            break
        elif target > sort_list[middle]:
            sort_list = sort_list[middle:]
        elif target < sort_list[middle]:
            sort_list = sort_list[:middle]
        else:
            return "Fount it", str(sort_list[middle])

    else:
        print "List is Empty"

arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
bee_search(arr,15)

推荐答案

可能这回答了您的部分问题.您实际上并不需要获取中间索引，您可以将alist和target中的最大值进行比较:

Probably this answers part of your question. You don't really need to get the middle index, you can compare the maximum value in alist with target:

def bee_search(alist, target):
    largest = max(alist)
    if target == largest: 
        print "Found", target
    elif target < largest: 
        print"Found", target
    else:                  # target > largest
        print("Not found")

在target == largest和target > largest时都可以，但在target < largest时不可以，是的，这是一个坏算法！

This is okay when target == largest and when target > largest but not when target < largest, yes this is a broken algorithm!

arr = [1,0,2,3, 10, 200, 5, 29, 10, 39, 109]
bee_search(arr, 30)

运行时，将显示以下输出:Found 30.

When run this is the output:Found 30.

此问题也适用于您的算法，简单的比较不能明确地告诉我们alist是否具有整数30的引用.您可能需要考虑解决方法，不要放弃.

This problem applies to your algorithm too, a simple comparison cannot tell us definitely whether alist has a reference for integer 30. You may need to consider workarounds, don't give up.

这篇关于优化二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！