算法之查找

一、列表查找：从列表中查找指定元素

• 输入：列表、待查找元素
• 输出：元素下标或未查找到元素

二、列表查找方式

• 顺序查找 ： 从列表的第一个元素开始遍历，知道找到为止。时间复杂度O(n)
• 二分查找 ：从有序的列表的候选区L[0:n]开始，通过堆待查找的值与候选区中间值进行比较，每次候选区数减少一半，时间复杂度O(logn)

顺序查找

def linear_search(data_set, value):
    for i in range(range(data_set)):
        if data_set[i] == value:
            return i
    return

三、二分查找

# 注意 二分查找的列表必须为有序列表
def binary_search(li, val):
    '''
    传入一个列表先取出中间值， 如果val大于中间值则向右查找否则向左查找
    '''
    low = 0
    high = len(li) - 1
    while low <= high:  # 候选区有值
        mid = (low + high) // 2  # 取中间值
        if li[mid] > val:
            high = mid - 1
        elif li[mid] < val:
            low = mid + 1
        else:
            return mid
    else
        return None

使用递归的方式实现

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

 四、查找练习

LetCode网站题目：

现有一个学员信息列表（按id增序排列），格式为：
stu_info = [
    {id:1001, "name":"张三", "age":20},
    {id:1002, "name":"李四", "age":25},
    {id:1004, "name":"王五", "age":23},
    {id:1007, "name":"赵六", "age":33}
]
修改二分查找代码，输入学生id，输出该学生在列表中的下标，并输出完整学生信息。

def binary_search2(li, val):
    '''
    传入一个列表先取出中间值， 如果val大于中间值则向右查找否则向左查找
    '''
    low = 0
    high = len(li) - 1

    while low <= high:
        mid = (low + high) // 2
        if li[mid]['id'] > val:
            high = mid - 1
        elif li[mid]['id'] < val:
            low = mid + 1
        else:
            return mid, li[mid]
    else:
        return '没找到学生'

print(binary_search2(stu_info, 1003))