几乎只要打开电脑，我们都用到了查找技术，像
百度一下，你就知道啦，这就是最典型的查找，但是不同的查找方法，会有不同的效率，或许对于小量级数据，算法的好坏并没有什么太大的区别，但是当数据的量级比较大的时候，一个好的查找方法就会有很大的优势，会节省很多的时间。今天就来让我们来体验集中查找技术吧。
目标：一个数组中有从0到999一千个数据元素，请找出值为900的下标
方法一：顺序表查找法（傻瓜式算法）
第一种方法，就是顺序遍历，不用脑子，从前往后依次遍历，知道遍历出结果，我称之为傻瓜式算法
代码
NSInteger account = 0; //记录总共执行了多少次
for (NSInteger i = 0; i < self.dataArr.count; i++) {
NSInteger num = [self.dataArr[i] integerValue];
account++;
if (num == 900) {
NSLog(@"%ld",account);
return;
}
}
0CF4B90F-B600-4428-8D1F-BDBDE670E8E0.png
由打印结果我们可以看到，总共执行了901次
方法二：折半查找（二分查找）
其实折半查找就是我们上一节提出的二叉树查找，在开始代码之前，我们先来介绍一下概念；
折半查找技术，又称为二分查找：它的前提是线性表中的记录必须是里面的值类型有序（从小到大，或者从大到小），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键值相等，则查找成功；如给定值小于中间值，则下次从中间左侧开始查找，反之右侧；不断重复上述过程，知道查找成功，或者区域无记录
代码
///第二种算法：折半查找
- (IBAction)SecondButton:(id)sender {
BOOL exist = NO;//记录值是否存在，默认不存在
NSInteger account = 0; //记录总共执行了多少次
NSInteger low = 0;//定义最低下表为记录首位
NSInteger height = self.dataArr.count - 1;//定义最好下标为记录末尾
//如果存在跳出，如果遍历结束，也跳出
while (!exist) {
account ++ ;
NSInteger mid = (low + height) / 2;//折半
if (mid == 0 || mid == self.dataArr.count - 1) {
//没有找到，跳出
exist = YES;
}
if (900 > [self.dataArr[mid] integerValue]) {
//如查找值比中间值大，最低下标调整到中位下标的下一位
low = mid + 1;
}else if (900 < [self.dataArr[mid] integerValue]){
//如查找值比中间值小，最高下标调整到中位下标的上一位
height = mid - 1;
}else if (900 == [self.dataArr[mid] integerValue]){
//找到下标元素
exist = YES;
}
}
NSLog(@"折半查找：总共执行了%ld次",account);
}
B387451A-4F40-43EE-B8B3-D3AD858DBB84.png
通过打印结果可知，这个仅仅执行了10次，比上一种算法效率相差了很多，一看便知。
方法三：插值查找
插值查找这个好像还真没有什么特别需要理解的地方，他就是先辈们对折半查找的NSInteger mid = (low + height) / 2这个方法进行了改进，具体改为了NSInteger mid = low + (height -low)*(key - arr[low])/(arr[height] - arr[low])。具体为啥这个推导，应该还是有原因的，但是数学基础不怎么好，对这个只能记住了。表示无可奈何啊😄😄😄
插值查找：是根据要查找的关键字key与查找表中最大最小值记录的关键字比较后的查找方法，其核心就是在于插值的计算公式(key - arr[low])/(arr[height] - arr[low])
代码
///第三种算法：插值查找
- (IBAction)ThirdButton:(id)sender {
BOOL exist = NO;//记录值是否存在，默认不存在
NSInteger account = 0; //记录总共执行了多少次
NSInteger low = 0;//定义最低下表为记录首位
NSInteger height = self.dataArr.count - 1;//定义最好下标为记录末尾
//如果存在跳出，如果遍历结束，也跳出
while (!exist) {
account ++ ;
NSInteger mid = low + (height - low)*(key-[self.dataArr[low] integerValue])/([self.dataArr[height] integerValue] - [self.dataArr[low] integerValue]);//插值
if (mid == 0 || mid == self.dataArr.count - 1) {
//没有找到，跳出
exist = YES;
}
if (key > [self.dataArr[mid] integerValue]) {
//如查找值比中间值大，最低下标调整到中位下标的下一位
low = mid + 1;
}else if (key < [self.dataArr[mid] integerValue]){
//如查找值比中间值小，最高下标调整到中位下标的上一位
height = mid - 1;
}else if (key == [self.dataArr[mid] integerValue]){
//找到下标元素
exist = YES;
NSLog(@"下标：%ld",mid);
}
}
NSLog(@"插值查找：总共执行了%ld次",account);
}
402C9E44-EE8C-4783-BF42-8CA7D0D30649.png
卧槽，这个算法还真是有用啊，看来古人诚不我欺也。 耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶耶
网友评论