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中如何实现二分查找，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注创新互联行业资讯频道。