问题

给出一个长度为 $n$ 的按升序排序的序列，询问一个数 $x$ 在序列中的出现位置，若未出现，则返回 $0$

解析

顺序查找

对于给定一个长度为 $n$ 的序列，要在其中寻找一个数，最简单的方法就是逐个遍历，当匹配到相应数后，返回对应下标，如果没有找到，则返回 $0$

二分查找

由于给出的是一个按升序排序的序列，对于任意的下标 $i$ ，如果 $a_i\le x$ 则所有的 $a_j,(j<i)$ 均不符合条件，每次可以尝试序列的中间项，每次查找问题规模缩小一半，找到值后返回，若问题规模缩小到 $0$ 时还没有找到答案，则返回 $0$

设计

顺序查找

search(a[],len,x)
    for i=1;i<=len;++i
        if a[i]==x:
            return i
        if a[i]>x:
            return 0
    return 0

二分查找

search(a[],len,x)
    l=1,r=len
    while l<=r:
        mid=(l+r)/2
        if a[mid]>=x:
            r=mid-1
        else
            l=mid+1
    if l>len
        return 0
    return l

分析

顺序查找

最优情况：
显然，当查找的元素正好是第一项的时候，顺序查找可以在 $O(1)$ 的复杂度内找到答案
最差情况：
显然，当不存在该元素,且该元素大于序列内所有数时，顺序查找需要遍历所有项，复杂度为 $O(n)$
平均：
设对于任意一个元素 $X$ ,序列中有 $x$ 个小于等于它的项，则找到 $X$ 需要 $x$ 次枚举
考虑对于其中的每一项 $a_i$ ,需要查找 $i$ 次，则对于整个序列，总查找次数为 $\frac{(1+n)\times n}{2}$ ,平局每一个 $x$ 的查找次数为 $\frac{(1+n)}{2}$
则平均复杂度为 $O(n)$

二分查找

每次查找时，至少会抛去 $\lfloor \frac n2 \rfloor$ 大小的区间，也就是说每一次问题规模缩小一般
令 $F(n)$ 记作问题规模为 $n$ 时的复杂度，可以列出表达式

$\left.\begin{cases} F(n)=F(\lfloor \frac n2 \rfloor)+1\\ F(\lfloor \frac n2 \rfloor)=F(\left\lfloor \frac{\lfloor \frac n2 \rfloor}{2} \right\rfloor)+1\\ F(1)=1\\ \end{cases}\right.$
所以问题就变成了一个数 $n$ 可以 $\div 2$ 多少次，显然是 $\log_{2}^{n}$ 次
所以最后的复杂度为 $O(\log_2^n)$

源码

传送门

算法课-搜索算法

问题

解析

顺序查找

二分查找

设计

顺序查找

二分查找

分析

顺序查找

二分查找

源码