Python中如何实现二分查找

本篇文章为大家展示了Python中如何实现二分查找，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

二分查找是一个用的非常多的查找算法，目的是从一个列表list里面，找到一个你想要的数，记做目标数据，返回这个数的索引，比如[5, 12, 3], 想找到12在哪，然后答案应该是1。直接的方法是从头开始，一个个比较，如果相等就返回，先拿5和12比， 不相等就继续下一个，12 = 12， 所以返回1，但是如果这个列表很大， 这样查找起来就比较慢，时间复杂度是O（n），而二分查找是一个比较高效的查找方法，数学里面学过二分法，我觉得道理是类似的。二分查找的时间复杂度是O（logn）。

二分查找的一般过程为先找到数组的中间数据，然后对比目标数据和中间数据，如果相等则返回中间数据，如果目标数据大于中间数据，则继续在列表的右边按照相同方法去寻找。否则在左边寻找；这里要注意的是，查找过程中的列表是经过排序以后的，所以这里比较的时候才会按大小去搜索。

下面是用Python实现二分查找的一个栗子

def binary_search(array, query_value):
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + (high - low) // 2
        mid_val = array[mid]
        if mid_val == query_value:
            return mid
        elif mid_val < query_value:
            low = mid + 1
        else:
            high = mid - 1
    return None


def main():
    array_1 = [1, 10, 20, 30, 180]
    print binary_search(array_1, 20)
    print "- * - " * 5
    array_2 = [2, 1, 3, 3, 5, 4, 1, 6]
    sorted_array = sorted(array_2)
    print "sorted_array : ", sorted_array
    print(binary_search(sorted_array, 5))


if __name__ == "__main__":
    main()

上述内容就是Python中如何实现二分查找，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。