数据结构与算法-查找算法

第二章 查找和排序算法
课时1：列表查找
1、列表查找的含义：从对象中查找某一个特定的元素
2、列表查找的方式包含两种：顺序查找和二分查找
3、顺序查找算法:从开始一直搜索到最后一个元素进行查找，for循环，时间复杂度为O（n）;
4、二分查找针对有效的列表直接进行首尾二分查找，不断使得候选区减半，所以其时间复杂度为O（logn）
4、二分查找只针对排序有序的列表查找有效高速，顺序查找针对任何列表；
5、由于二分查找算法一般都需要进行排序，而排序算法的时间复杂度一般大于O（n）,高于顺序查找；所以在内置的函数index中采用的依旧是顺序查表；

#导入函数运行时间测试函数from cal_time import *#查找算法#顺序查找/线性查找算法的含义@cal_timedef linear_search(l,v):    for i in range(len(l)):        if l[i]==v:            return i#二分查找算法（有序的排列列表之下使用二分法）@cal_timedef binary_search(l,v):    left=0    right=len(l)-1    while(left<right):        mid = (left + right) // 2        if l[mid]==v:            return mid        elif l[mid]<v:            left=mid+1        else:            right=mid-1l=list(range(10000))v=3890binary_search(l,v)linear_search(l,v)