当数组（或其他查找的对象）是杂乱无章之时，或许查找起来就会比较困难，甚至只能一个一个找。但是，当数据是有序的之后，查找数据就有更为省时的算法了

二分查找

二分查找也被称之为折半查找，其绝对是应用最为广泛也的查找算法了，其 \(log(N)\) 的时间复杂度也是相当优秀，所以其名声也是相当大，以至于我在很久之前就听说过此算法并写了一篇博文，可以点击链接直接跳转

插值查找

插值查找是在二分查找的基础上改进产生的，其大致思路如下：当我们查字典时，如果首字母为 a ，我们必然不会往中间翻，而是翻向靠前的页数，所以，当我们进行查找之时，也可以根据具体情况进行镶银的调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BinarySearch(int a[],int size,int p) {
    int L = 0; 
    int R = size - 1; 
    while( L <= R) {
        int mid = L + (R-L) * (p-a[L]) / a[R] - a[L]; 
        if( p == a[mid] )
            return mid;
        else if( p > a[mid])
            L = mid + 1; 
        else
            R = mid - 1;
    }
    return -1;
}

说明：

  1. 插值查找的实质就是 根据key值于表中最大最小值比较后的查找方法，其核心为插值计算公式——\(\frac {key-a[low]} {a[hight]- {a[long]}}\)
  2. 其对于较为均匀排列的查找表有更好的效率，而对极端不均匀的数据来说可能不是很好的选择

斐波那契查找

既然有了二分查找这样的思路，二分查找是以中间作为划分的，插值查找是依据插值计算公式进行划分的，那么我们同样可以试图采用别的划分方法，比如：斐波那契数列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int FibSearsh(int* a, int n, int key) {
    const int F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    int low = 1, high = n, mid, i, k = 0;
    while (n > F[k] - 1)
        k++;
    for (i = n; i < F[k] - 1; i++)
        a[i] = a[n];
    while (low <= high) {
        mid = low + F[k-1] - 1;
        if (key < a[mid]) {
            high = mid - 1;
            k -= 1;
        } else if (key > a[mid]) {
            low = mid + 1;
            k -= 2;
        } else {
            if (mid <= n)
                return mid;
            else
                return n;
        }
    }
    return -1;
}

二叉搜索树

这是利用二叉树来进行查找的算法，相关内容可点击链接直接跳转