=========================================

二分查找

是一个在有序元素列表中的查找的算法
原理：如这个列表长度是10000，通过算法排除不满足条件的另一半来查找。

比如从100个数字中找到某个数字的索引，可以先找到50进行比较来缩小范围。如果大于50就再拿75做比较，以此类推，直到找到该数字。

这样的二分算法能从原先的暴力查找（最坏情况下）100次减少到7次。

记做公式：
$$log_2 n$$

算法运行时间

运行时间的增速:随着数据量的增加，运行时间会出现递增的情况。优秀的算法增速越少，比如二分查找和简单查找在10亿个算法的情况下，简单查找需要11天才能查找玩，而二分查找只需要32毫秒。

算法的速度指的的操作数的增速。也就是时间复杂度

数组

缺点：添加新元素如果遇到内存空间被占用，需要额外申请空间，效率会降低。频繁插入和删除操作不适合数组。

链表

优点：每个元素都存储着下一个元素的地址，如果是有序的读取那读取速度将快于数组。适合大批量列表

如果是有序读取，插入操作频繁的话是链表占优
如果是无序读取，插入操作比较少的话是数组占优

数组：
读取：O(1)
插入：O(n)
删除：O(n)

链表：
读取：O(n)
插入：O(1)
删除：O(1)

选择排序例题

对一个数组进行从小到大排列
思路就是遍历整个数组，将每个数字与其他数字进行比较。选择排序的优化在于第一轮被拿出来做比较确定为最小的数字将会被踢出数组，不会参与到下一轮的比较。

def smallest(list):           
    small_value = list[0]       
    small_index = 0              

    for i in range(1,len(list)): 
        if list[i] < small_value: 
        small_value = list[i] 
        small_index = i
        return small_index
      # 选择排序                    

def select_sort(list): 
  newlist = []                
  for i in range(len(list)):
    small = smallest(list)
    newlist.append(list.pop(small))
  return newlist             

小结

• 需要存储多个元素时可以考虑使用数组或者链表，时刻记得他们之间的优缺点。
• 数组的读取速度很快
• 链表的插入和删除速度很快