查找之顺序查找与二分查找

查找一般来说是在某个对象(列表、集合等)中找到指定的元素所在位置。

顺序查找

顺序查找的时间复杂度为O(n)，实现如下:

def linear_search(li, val):
    """
    遍历并比较，找到合适的值的索引并返回
    """
    for index, value in li:
        if value == val:
            return index
    else:
        return None

二分查找

二分查找的时间复杂度为O(logn)，但前提是只能对经过排序后的列表产生作用，如果拿到的是未经排序的列表，那么对列表进行排序的时间复杂度为O(n)。假定拿到的是已经排好序的列表，那么二分法实现如下:

def binary_search(li, val):
    """
    每次取中间值，找到待索引区域
    直到找到指定的值或没有中间值为止
    """
    left = 0
    right = len(li) - 1
    
    while right >= left:
        mid = (left + right) // 2
        value = li[mid]

        if value == val:
            return mid
        elif value > val:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None