折半查找法

折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大)，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找，不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

假设现在有这样一个有序数组{0,1,16,24,35,47,59,62,73,88,99}，对它进行查找是否存在62这个数，我们来看折半查找的算法是如何工作的。

/* 折半查找 **/
- (NSInteger)binary_search:(NSArray *)targetArray key:(NSInteger)key {
    NSInteger low,high,mid;
    low = 0;  /*定义最低下标为记录首位*/
    high = targetArray.count-1;  /*记录最高下标为记录末位*/
    while (low <= high) {
        mid = (low + high)/2;   /*折半*/
        if (key < [targetArray[mid] integerValue]) { /*若查找值比中值小*/
            high = mid-1;  /*最高下标调整到中位下标小一位*/
        }else if (key > [targetArray[mid] integerValue]) {  /*若查找值比中值大*/
            low = mid+1;  /*最低下标调整到中位下标大一位*/
        }else {
            return mid;   /*若相等则说明mid即为查找到的位置*/
        }
    }
    return -1;
}

具体执行步骤为：

1.程序开始运行，参数targetArray={0,1,16,24,35,47,59,62,73,88,99}, key=62,初始化时，此时low=1,high=10,如图所示。



2.开始循环，进行查找。
3.开始折半，mid计算得5，由于[targetArray[5] integerValue]=47<key,所以执行了low = mid+1，low=6,如图所示。



4.再次循环， mid=(6+10)/2=8,此时[targetArray[8] integerValue]=73>key,所以执行high = mid-1，high=7,如图所示。



5.再次循环，mid=(6+7)/2=6,此时[targetArray[6] integerValue]=59<key,所以执行了low = mid+1，low=7,如图所示。



6.再次循环，mid=(7+7)/2=7, 此时[targetArray[7] integerValue]=62=key,查找成功，返回7.

该算法还是比较容易理解的，同时它的效率也是非常的高，但到底有多高，我们来计算此算法的时间复杂度。

首先， 将这个数组的查找过程绘制成一棵二叉树，如图所示，从图中可以理解，如果查找的关键字不是中间记录47的话，折半查找等于是把静态有序查找表分成了两棵子树，即查找结果只需要找其中的一半数据即可，等于工作量减少了一半，然后继续折半查找，效率当然是非常高了。



由“具有n个结点的完全二叉树的深度为「log2n」+1” 可以看出，查找关键字的最坏为「log2n」+1 最好情况为1 所以折半算法的时间复杂度为0(logn),它显然好于顺序查找的O(n)时间复杂度了。

不过由于折半查找的前提条件是需要有序顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了，但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

插值查找

如果对折半查找的第8句代码进行改造，得到如下公式mid=(low+high)/2=low+(high-low)/2;
也就是mid等于最低下标low加上最高下标high与low的差的一半，再进一步的改进得到如下方案：mid=low+(high-low)*(key-targetArray[low])/(targetArray[high]-targetArray[low]);
这就是插值查找的算法。

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字做比较后的查找方法，其核心就在于插值的计算公式：
（key-targetArray[low]）/(targetArray[high]-targetArray[low])。 应该说从时间复杂度来看，它也是O(logn),但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多，反之，数组中如果分布类似{0,1,2,2000,200,…..,999998,999999}这种极端不均匀的数据，用插值查找未必是最合适的选择。

斐波那契查找

斐波那契查找(Fibonacci Search)，它是利用了黄金分割原理来实现的。斐波那契数列：



上代码：

/* 斐波那契查找 */
1  - (NSInteger)fibonacci_Search:(NSMutableArray *)targetArray key:(NSInteger)key {
2     NSArray *F = @[@0,@1,@1,@2,@3,@5,@8,@13,@21,@34];  /*斐波那契数列*/
3     NSInteger low,high,mid,i,k,n;
4     low = 0;  /*定义最低下标为记录首位*/
5     high = targetArray.count-1;  /*定义最高下标为记录末位*/
6     k = 0;
7     n = targetArray.count-1;
8     while (n > [F[k] integerValue] - 1) {
9         k++;
10    }
11    for (i = n; i<[F[k] integerValue]-1; i++) {  /*将不满的数值补齐*/
12        targetArray[i]=targetArray[n];
13    }

14    while (low <= high) {
15        mid = low + [F[k-1] integerValue] - 1;  /*计算当前分割的下标*/
16        if (key < [targetArray[mid] integerValue]) {  /*若查找记录小于当前分割记录*/
17            high = mid - 1;   /*最高下标调整到分割下标mid-1处*/
18            k = k - 1;  /*斐波那契数列下标减一位*/
19        }else if (key > [targetArray[mid] integerValue]) {  /*若查找记录大于当前分割记录*/
20            low = mid + 1;   /*最低下标调整到分割下标mid+1处*/
21            k = k - 2;   /*斐波那契数列下标减两位*/
22        }else {
23            if (mid <= n) {
24                return mid;  /*若相等则说明mid即为查找到的位置*/
25            }else {
26                return n;   /*若mid>n说明是补全数值，返回n*/
27            }
28        }
29    }
30    return -1;
31  }

1.程序开始运行，参数targetArray={0,1,16,24,35,47,59,62,73,88,99},要查找的关键字key=59。注意此时我们已经有了事先计算好的全局变量数值F的具体数据，它的斐波那契数列，F={0,1,1,2,3,5,8,13,21,…..}。



2.第6~10行是计算当前的n处于斐波那契数列的位置，现在n=10，F[6]<n<F[7],所以计算得出k=7。

3.第11~13行，由于k=7,计算时是以F[7]=13
为基础，而a中最大的仅是a[10],后面的a[11],a[12]均为赋值，这不能构成有序数列，因此将它们都赋值为最大的数值值，所以此时a[11]=a[12]=a[10]=99。

4.第14~29行查找正式开始。

5.第15行，mid=0+F[7-1]-1=7,也就是说，我们第一个要对比的数值是从下标为7开始的。

6.由于此时key=59 而targetArray[7]=62,因此执行第17~18行，得到high=6,k=6,



7.再次循环，mid=0+F[6-1]-1=4。此时targetArray[4]=35<key,因此执行20~21行，得到low=4+1=5,k=6-2=4,注意此时k下调2个单位。



8.再次循环，mid=5+F[4-1]-1=6。此时targetArray[6]=59=key,因此执行第24行，返回mid=6。程序结束运行。

斐波那契查找算法的核心在于：

  1. 当key=targetArray[mid]时，查找就成功；
  2. 当key=targetArray[mid]时,新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
  3. 当key>targetArray[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。


也就是说，如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些，所以尽管斐波那契查找的时间复杂度也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果最坏情况，比如这里key=1,那么始终都处于左侧长半区在查找，则查找效率要低折半查找。

还有比较关键的一点，折半查找是进行加法与除法运算(mid=(low+high)/2)，插值查找进行复杂的四则运算(mid=low+(high-low)*(key-targetArray[high]-targetArray[low])),而斐波那契查找只是最简单加减法运算(mid=low+F[k-1]-1),在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

以上三种有序表的查找本质上是分割点的选择不同，各有各的优劣，实际开发中，可以根据数据的特点综合考虑再做出选择。