二分查找

是一种分治算法，每次将数组分为大小相等的部分。很熟悉就不用介绍了。时间复杂度为 $O(\lg n)$ 。
示例伪代码：

binary_search(A, n, T)
{
    L = 0
    R = n − 1
    while (L <= R){
        m = floor((L + R) / 2)
        if (A[m] < T){
            L = m + 1
        }else if (A[m] > T){
            R = m - 1
        }else{
            return m
        }
    }
    return unsuccessful
}

斐波那契查找

类似二分查找，同样是分治算法。但不是等份划分数组，而是使用斐波那契数来缩小搜索范围。平均和最坏的时间复杂度为 $O(\lg n)$ 。
平均而言，同二分查找相比，执行比较的操作增加了4%（参考维基百科）。
优点是只需要用到加减法来计算数组索引，而二分搜索需要用到移位或者除法计算数组索引。

指数搜索

指数搜索时间复杂度为 $O(\lg i)$ ， $i$ 为搜索元素在数组中的索引位置。

原始算法包含两个阶段：

确定搜索元素 $key$ 位于数组中的范围，假定数组是按升序排序，首先查找第一个满足条件的指数 $j$ ， $j$ 每次自加 1，要满足的条件为 $key\le a[2^j]$ 。由于是第一个满足条件的 $j$ ，所以有 $a[2^{j-1}]<key\le a[2^j]$ 成立。
以 $2^{j-1}$ 为下界， $2^j$ 为上界，在范围内执行二分查找。

示例伪代码：

exponential_search(arr, size, key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;//可以改为左移运算
    }

    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

算法的变种

为了更快的确定搜索元素所在的范围，在原始算法的第一阶段前加一个阶段，这样变种的指数搜索算法就分为了三个阶段。
新的第一阶段，与之前类似，同样是确定第一个满足条件的指数 $j^*$ ，条件同样为 $key\le a[2^{j^*}]$ ，但是和之前每次自加1不同， $j^*$ 是每次自乘2（即从 $2^4$ 变为了 $2^8$ 而非 $2^5$ ）。所以有 $a[2^{j^*/2}]<key\le a[2^{j^*}]$ 。相较于之前，新的第一阶段更快的确定了一个更粗糙的上下界。
接着在这个较为粗糙的上下界 $(2^{j^*/2},2^{j^*}]$ 上执行原始的指数搜索算法，即确定一个更精确的上下界 $(2^{j-1},2^j]$ ，并在更精确的上下界上面执行二分查找。