Objective-C实现二分查找和插值查找
二分查找
二分查找 又称折半查找，要求数组必须是有序的数列，是一种有序查找算法。二分查找的时间复杂度是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;
}