算法笔记_常用查找总结

顺序查找(线性查找)

从第一个元素开始，顺序进行搜索，直到找到元素或者搜素到最后一个元素。

时间复杂度：O(n)
内置函数为：index()

def linear_search(li, val):
    for ind, v in enumerate(li):
        if v == val:
            return ind
        else:
            return None

二分查找(折半查找)

它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用**顺序**存储结构，而且表中元素按关键字有序排列

时间复杂度：O(logn)

def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:	# 列表有值存在
        mid = (left + right) // 2	
        if li[mid] < val:	# 和中间值比较
            left = mid + 1
        elif li[mid] > val:
            right = mid - 1
        else:
            return mid
    else:
        return None