今天分享一道简单的笔试题，题目来源于京东校园招聘笔试真题。你做出这道简单的题目需要花费多少东呢？
题目描述
有一个有序表为 {1，5，8，11，19，22，31，35，40，45，48，49，50} ，当二分查找值为 48 的结点时，查找成功需要比较的次数（ ）
A、4
B、3
C、2
D、1
题目分析
一道送分题。
有序表的长度为 13，根据 二分查找法 查找数的特性，每次都  n/2 进行折半查找。
13 / 2 = 6
6 / 2 = 3
3 / 2 = 1
1 / 2 = 0
最多需要 4 次就能得出结果。
列表下标索引从零开始标记。
这道题目需要查找的是 48 。
第一次，求出 [0，12] 中间节点。
0 + （12 - 0） / 2 = 6 

a[6] = 31 < 48
区间变为 [7，12]。
第二次，求出 [7，12] 中间节点。
7 + （12 - 7） / 2 = 9 

a[9] = 45 < 48
区间变为 [10，12]。
第三次，求出 [10，12] 中间节点。
10 + （12 - 10） / 2 = 11 

a[11] = 49 > 48
区间变为 [10，11]。
第四次，求出 [10，11] 中间节点。
10 + （11 - 10） / 2 = 10

a[10] = 48 = 48
找到啦！
我的个人博客大改版，200 篇原创算法等你来看！
五分钟学算法-和程序员小吴一起学算法​www.cxyxiaowu.com

顺序表查找

有序表查找

对顺序表进行二分查找
索引顺序查找表

索引顺序查找表也就是分块查找
把线性表分为若干块，每一块的关键字都小于下一块的最小关键字。
索引按顺序排列进行二分查找，在对找到的块进行顺序查找

顺序查找
基本思想
属于线性查找和无序查找，从一端开始顺序扫描，直到找到与目标值value相等的元素。
这是最基本的查找方法，也是时间复杂度最高的查找算法。
在数据过多时，这种方法并不适用。
代码实现
分块查找
基本思想
属于顺序查找的改进方法，又叫索引顺序查找。
将n个元素分成m块(m<=n)，每个块中元素可以没有顺序，但是m个块之间是有序排列，所以特别适合于节点动态变化的情况。
分块查找的速度虽然不如二分查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
那么索引表的构成就是每个块中的最大元素。
查找方式是先对索引表进行二分或顺序查找，选出目标值应该所在的块，然后在块内进行顺序查找。
二分查找
基本思想
属于有序查找算法，也叫折半查找，就是将数组每次选取一半进行查找，怎么选取一半就需要让中间值与目标值value进行比较，因为有序，所以中间值小于目标值则选取后半部分，大于目标值则选取前半部分，依此类推，直到找出与目标值相等的元素，否则返回-1或null。
这种方法有效的缩减查找次数和查找范围，适用于数据量比较大的有序表。
因为前提是有序表，所以对于插入删除等操作过多的数据集并不适用，因为在排序算法上浪费的时间会比较多。
一般的时间复杂度是O(log2n)
代码实现
插值查找
基本思想
属于二分查找的改进版，二分查找一直重复一半一半的操作，这种操作比较固定，并不会根据目标值的大小进行自适应分段和选择，而插值查找可以根据目标值value进行自适应。
下面是百度词条对插值的解释：插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起。
既然是二分查找的改进版，那么就要找关键点进行改进，二分是取1/2的有序表进行查找，那么mid就是关键点，二分中mid=(low+high)/2，可以转化成mid=low+(high-low)/2，所以相当于(high-low)/2中的1/2就是所分的比例，那么可以对mid进行改进，mid=low+low+(value-list[low])/(list[high]-list[low])*(high-low)，(value-list[low])/(list[high]-list[low])就是所分的比例。
根据目标值在整个有序表中所处的位置，让mid的变化更靠近目标值value，这样也就间接地减少了比较次数。
这种方法适用于关键字分布均匀的有序表。
复杂度为O(log2(log2n))
代码实现
斐波那契查找
基本思想
斐波那契数列与0.618有着奇妙的关联，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，所以可以将黄金比例运用到查找中。
百度词条：斐波那契搜索，斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F(n)，将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
这个方法比较重要，所以百度词条上讲的很清楚！
代码实现
总结
还剩下两种非常重要的查找算法，就是树表和哈希，这两种我就单独写，ball ball大佬们不要嫌弃！

1.二分查找

二分查找又叫折半查找，它的前提是线性表中的记录必须是关键码有序（通常从小到大有序，线性表必须采用顺序存储）。

假设有一个有序表数组{0,1,16,24,35,47,59,62,73,88,99}，共10个数字，对其进行查找是否存在62这个数。

/* 二分查找 */
int Binary_Search(int *a, int n, int Key)
{
    int low, high, mid;
    low = 1; //定义最低小标为记录首位
    high = n; //定义最高下标为记录末位
    while(low <= high)
    {
        mid = ( low+high )/2;   //折半
        if(Key<a[mid])          //若查找值比中值小
            high = mid-1;       //最高下标调整到中位小一位
        else if (Key>a[mid])
            low = mid+1;       
        else 
            return mid;  //若相等即说明mid为查找的位置
    }
    return 0;
}

二分查找的时间复杂度为O(logn)，优于顺序查找O(n)。

2.插值查找

二分查找的中值选取条件为：

改进方法：

插值查找的代码为：

mid = low+ (high-low) * (key-a[low]/a[high]-a[low])

算法时间复杂度同为O(logn)，当表长度较大且关键字分布比较均匀时，使用插值查找方法效果较好！

3.斐波那契查找

Fibonacci Search 是通过黄金分割原理进行实现的。代码如下：

/* Fibonacci Search */
int Fibonacc_Search(int *a, int n, int Key)
{
    int low,high,mid,i,k;
    low = 1;    //定义最低下标为记录首位
    high = n;   //定义最高下标为记录末位
    k = 0;
    while(n>F[k]-1)   //计算n位于Fibonacci数列中的位置
        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; //最高下标调整到分隔符下标mid-1处
            k = k-1;  //Fibonacci数列下标减一位
        }
        else if (key>a[mid])  //若查找记录大于当前分隔符
        {
            low = mid+1; //最低下标调整到分隔符下标mid+1处
            k = k-2;
        }
        else
        {
            if(mid<=n)
                return mid; //若相等则说明mid即为查找的位置
            else
                return n; //若mid>n，说明是补全数值，返回n
        }
    }
    return 0;
}

三种有序表的查找本质上是分隔点的选择不同，各有优劣。