算法图解

1. 算法简介

   1. 二分查找

      1. 更佳的查找方式
         当你在一个有序列表中查找一个元素时,有很多种查找方法,其中最佳的方法就是二分查找法—每次都找最中间的,依据与所找值的大小关系,排除另一半的值.这样对于包含n个元素的列表,最多只需log2n步,即其时间复杂度为O(logn).

         def binary_search(list, item):
            low = 0
            high = len(list) - 1
            while low <= high:
                mid = (low + high) / 2
                guess = list[mid]
                if guess == item:
                   return mid
                if guess > item:
                   high = mid - 1
                else:
                   low = mid + 1
            return None

      2. 运行时间
         只需要对数时间.

   2. 大O表示法