1. 顺序查找

算法介绍
对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。
代码实现

# 查找目标值在给定列表的位置
def sequence_search(list, target):
    length = len(list)
    for i in range(length):
        if list[i] == target:
            return i
    return -1

复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)

2. 二分查找

算法要求
1.必须采用顺序存储结构
2.必须按关键字大小有序排列。

算法介绍
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录时查找成功，或直到子表不存在为止，此时查找不成功。

代码实现

迭代实现(推荐)

def binary_search(lis, target):
    low = 0
    high = len(lis) - 1
    while low <= high:
        mid = int((low + high) / 2)
        if lis[mid] == target:
            return mid
        elif lis[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

复杂度分析

时间复杂度：O(logn),由于是每次折半，故需要log₂ⁿ次退出循环，所以复杂度为O(logn)
空间复杂度：O(1)

递归实现

def binary_search(lis, target, left, right):
    if left > right:
        return -1
    mid = int((left + right) / 2)
    if lis[mid] == target:
        return mid
    elif lis[mid] < target:
        return binary_search(lis, target, mid + 1, right)
    else:
        return binary_search(lis, target, left, mid - 1)

该方法是一种实现思路，但由于使用了递归，反而导致空间复杂度升为O(logn),故不推荐使用。