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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 复赛1005&&HDU 6148 Valley Numer【数位dp】

Valley Numer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

2864
来自专栏黑泽君的专栏

Java语言中:float数据类型在内存中是怎么存储的?

============================================================================= ja...

1661
来自专栏C语言C++游戏编程

这是C语言无法修改得东西,C语言基础教程之常量解析

常量可以是任何基本数据类型,如整数常量,浮点常量,字符常量或字符串文字,还有枚举常量。

981
来自专栏绿巨人专栏

读书笔记: 范畴论

一个范畴是一个带标签的有向图,其节点为对象(object),带有标签的有向边为箭头(arrow or morphism)。

1772
来自专栏智能算法

前端面试中的常见的算法问题

作者:Jack Pu 链接:www.jackpu.com/qian-duan-mian-shi-zhong-de-chang-jian-de-suan-fa-w...

4928
来自专栏数据结构与算法

字符串hash入门

简单介绍一下字符串hash 相信大家对于hash都不陌生 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在...

5715
来自专栏Java开发者杂谈

遍历算法(1)

遍历算法主要用在在处理迷宫问题,图,最短路径,以及枚举所有可能等问题上。下面我们通过一个简单的例子,来入门深度优先和广度优先算法: 1 package co...

3636
来自专栏大数据和云计算技术

二分查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第5篇《二分查找》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基础#...

36210
来自专栏JavaEdge

网易17校招编程笔试题Java解法赏析(更新至第9题)1 合唱团(动态规划)编程实现 3Fibonacci数列4数字反转5下厨房67喜欢的数字8买苹果9

5206
来自专栏小樱的经验随笔

浅谈数据结构之主席树(线段树进阶版)

今天看了点主席树的概念,加上飞哥上次讲的,目前对主席树有了大致的了解,简单谈谈吧,不讲代码,只讲思路,日后贴题!       Orz高级数据结构发明者主席!!最...

2845

扫码关注云+社区

领取腾讯云代金券