python算法和数据结构——查找

##查找

• 查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
• 列表���找（线性表查找）：从列表中查找指定元素  

              >输入:列表、待查找元素

              >输出：元素下标（未找到元素时一般返回None或-1）  

  • 内置列表查找函数：index（）

    ##（一）顺序查找

    • 顺序查找：也叫线性查找，从列表的第一个元素开始，顺序进行搜索，直到找到元素或搜索到最后一个元素为止。
    • 时间复杂度：O（n）    
    • 代码

    • def linear_search(lt,val):    for ind,v in enumerate(lt):        if v == val:            return ind        else:            return Noneprint(linear_search([1,2,3,4,5,6,7,8,9],3))

      ps：enumerate()是python的内置函数

      enumerate在字典上是枚举、列举的意思

      对于一个可迭代的（iterable）/可遍历的对象（如列表、字符串），enumerate将其组成一个索引序列，利用它可以同时获得索引 index和值value

      enumerate多用于在for循环中得到计数： for...in enumerate()                                                     

        ##（二）二分查找

      • 二分查找：又叫做折半查找，从有序列表的初始候选区lt[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
      • 从一下列表查找3，如图：                                                                                                           
      • 时间复杂度：o（n）=logn
      • 代码                                                                                                                                             

        def bin_search(a_list,val):    low=0    high=len(a_list)-1    while low = val:            high=mid-1        else:            low=mid+1print(bin_search([1,2,3,4,5,6,7,8,9],3))

        ##（三）顺序查找与二分查找的比较

      • 二分查找比线性查找的效率高，因为o（n）=logn