查找算法

顺序查找（线性查找）

1. 思想：根据列表下标的顺序，一步步查找列表中的元素是否有与需查找元素相对应，有则返回下标。
2. 代码实现

# 顺序查找
def linear_search(li,e):
    for ind,val in enumerate(li):
        if val == e:
            return ind
    else:
        return None
li = list(range(10))
import random
random.shuffle(li)
print(li)
print(linear_search(li,8))

3. 时间复杂度：O(n)（对列表元素进行一次遍历）

二分查找

1. 思想:前提为有序列表，对列表进行平均分割，当待找元素大于分割界为下标的元素时，往分割线的后半部分进行查找，否则往分割线前半部分查找
2. 代码实现

# 折半查找
def binary_search(li,value):
    left=0                      # 设置左边下标
    right=len(li)-1             # 设置右边下标
    while left<=right:          # 当剩余元素不为0时
        mid=(left+right)//2     # 设置中间下标（以中间下标的值作为分裂口）
        if li[mid]>value:
            right=mid-1
        elif li[mid]<value:
            left=mid+1
        else:
            return mid
    else:
        return None
li = list(range(50))
print(li)
print(binary_search(li,20))

3. 时间复杂度：O(nlogn)（存在折半查找）