Python查找算法之线性查找

简介

从列表的第一个元素开始，顺序搜索，直到查找到元素或者查找到列表最后一个元素为止。

时间复杂度

O(n)

列表的index方法

列表中的index()方法就是线性查找。
不用二分查找的原因是传递的列表不能保证是有序的，
如果内部进行排序的话，排序复杂度 > O(n)

代码示例

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""线性查找

从列表的第一个元素开始，顺序搜索，直到查找到元素或者查找到列表最后一个元素为止

时间复杂度：O(n)

列表的index()方法，就是线性查找

为什么不用二分查找呢？
    不能保证传递的列表是有序的
"""
import random


def linear_search(ls, val):
    """线性查找
    Args:
        :param ls: seq, 用于查找的列表
        :param val: any, 待查找的值
    Returns:
        int, 查找到，返回对应的索引
        int, 未找到，返回-1
    """

    for index in range(len(ls)):
        if ls[index] == val:
            return index
    else:
        return -1


ls = list(range(10))

random.shuffle(ls)
print(ls)

print(linear_search(ls, 5))