顺序查找

也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止

#查找某个元素的下标
def linear_search(data_list,val):
    for index,v in enumerate(data_list):
        if v == val:
            return index
    else:
        return None

print(linear_search(['a','b','c'],'c'))

时间复杂度：O(n)

二分查找

也叫折半查找，从有序列表的初始候选区list[0:n]开始，比较目标值和候选区中间值，使候选区减少一半。时间复杂度logn

• 方法1

def bin_search(li,val):
    """
    :param li: 源数组
    :param val: 目标值
    :return: 目标值的下标，未找到返回None
    """
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = (low + high) // 2
        if li[mid] == val:
            return mid
        elif li[mid] < val:
            low = mid + 1
        else: # li(mid) > val
            high = mid - 1
    return None

关键词：有序列表、候选区(low~high之间)、low和high的关系
bin_search([1,2,3,4,5],3.5)，初始图：

image.png
此时mid=2，第一次比较后low=3

此时mid=3，第二次比较后high=3

此时mid=3，第三次比较后high=2，这时候选区已经空了，所以终止条件是while low <= high

假设要找的目标值是4.5，只有最后一步不同，候选区还是空了，所以条件还是while low <= high

• 方法2，使用递归方式

def bin_search_rec(li,val,low,high):
    if low <= high:
        mid = (low + high) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            return bin_search_rec(li,val,low,mid - 1)
        else:
            return bin_search_rec(li,val,mid + 1,high)
    else:
        return None

总结

在python一些常用的查找比如val in list、list.index()、str.find()都是线性查找，因为源数据不一定是有序的，所以没法用二分查找