二分查找
二分查找 又称折半查找，要求数组必须是有序的数列，是一种有序查找算法。二分查找的时间复杂度是O(log n)。它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

它的基本思想是：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x < a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

有时候面试题会这样出：
给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

插值查找
插值查找是对二分查找的优化，是一种优秀的二分查找算法。插值查找也要求待查找的数组是有序的数列，是一种有序查找算法。
注： 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比，我们可以将查找的点改进为如下：
mid=low+ (key-a[low])/(a[high]-a[low]) *(high-low)，
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

基本思想： 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找.

/**
 * 二分查找循环实现
 */
- (NSUInteger)binarySearch:(NSArray<NSNumber *> *)srcArray number:(NSNumber *)des {
    NSUInteger low = 0;
    NSUInteger high = srcArray.count - 1;
    NSInteger middle = 0;
    while (low <= high && low <= srcArray.count - 1 && high <= srcArray.count - 1) {
        middle = (low + high) >> 1;
        // 或者
        // middle = ((high - low) >> 1) + low;
        if ([des integerValue] == [srcArray[middle] integerValue]) {
            return middle;
        } else if ([des integerValue] < [srcArray[middle] integerValue]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}

/**
 * 二分查找递归实现
 */

- (NSUInteger)binarySearch:(NSArray<NSNumber *> *)srcArray key:(NSNumber *)key low:(NSUInteger)low high:(NSUInteger)high {
    // 防止low和high越界
    if (low > high || low > srcArray.count - 1 || high > srcArray.count - 1) {
        return -1;
    }
    NSUInteger middle = (low + high) >> 1;
    if (srcArray[middle] == key) {
        return middle;
    } else if (srcArray[middle] > key) {
        return [self binarySearch:srcArray key:key low:low high:middle - 1];
    } else {
        return [self binarySearch:srcArray key:key low:middle + 1 high:high];
    }
    
    return -1;
}

/**
 * 插值查找循环实现
 */
- (NSUInteger)insertSearch:(NSArray<NSNumber *> *)srcArray number:(NSNumber *)des {
    NSUInteger low = 0;
    NSUInteger high = srcArray.count - 1;
    NSInteger middle = 0;
    while (low <= high && low <= srcArray.count - 1 && high <= srcArray.count - 1) {
        middle = low + ([des integerValue] - [srcArray[low] integerValue])/([srcArray[high] integerValue] - [srcArray[low] integerValue]) * (high - low);
        // 防止middle越界
        if (middle > high || middle < low) {
            return  -1;
        }
        if ([des integerValue] == [srcArray[middle] integerValue]) {
            return middle;
        } else if ([des integerValue] < [srcArray[middle] integerValue]) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}

/**
 * 插值查找递归实现
 */

- (NSUInteger)insertSearch:(NSArray<NSNumber *> *)srcArray key:(NSNumber *)des low:(NSUInteger)low high:(NSUInteger)high {
    // 防止low和high越界
    if (low > high || low > srcArray.count - 1 || high > srcArray.count - 1) {
        return -1;
    }
    
    NSUInteger middle = low + ([des integerValue] - [srcArray[low] integerValue])/([srcArray[high] integerValue] - [srcArray[low] integerValue]) * (high - low);
    // 防止middle越界
    if (middle > high || middle < low) {
        return -1;
    }
    if ([srcArray[middle] integerValue]  == [des integerValue]) {
        return middle;
    } else if (srcArray[middle] > des) {
        return [self insertSearch:srcArray key:des low:low high:middle - 1];
    } else {
        return [self insertSearch:srcArray key:des low:middle + 1 high:high];
    }
    return -1;
}

文／VV木公子（简书作者）
PS:如非特别说明，所有文章均为原创作品，著作权归作者所有，转载请联系作者获得授权，并注明出处，所有打赏均归本人所有！

如果您是iOS开发者，或者对本篇文章感兴趣，请关注本人，后续会更新更多相关文章！敬请期待！