算法-哨兵查找法(OC、Swift、Python)

蒙娜丽胖· 2019-10-21

在这里插入图片描述

前言

我们在一个数组中想查找某个对象item我们改如何操作呢?很简单一层遍历就可以搞定了,如下:

- (NSInteger)searchNormal:(NSArray *)array item:(NSString *)item{
    for(int i = 0;i<array.count;i++){
        if(array[i] == item){
            return i;
        }
    }
    return -1;
}

但是我们有没有更优的算法来查找呢?

在数据结构的书中我们可以找到“哨兵查找法”,但是什么又是“哨兵查找法”呢?什么又是“哨兵”呢?

所谓“哨兵”就是用一个特殊的值来作为数组的边界key,可以少用一条判断语句,目的在于免去查找过程中每一步都要检测整个表是否查找完毕,以达到提高程序的效率。

相对于一层遍历,没有使用”哨兵“的,是有两个判断条件的i<array.count和if(array[i] == item);但是使用了”哨兵“只有一个判断条件if(array[i] == item)!

如果你的数据量非常小的话,相对于一层遍历来说,差别微乎其微,但是当数据达到十万或者更多的时候,函数的执行时间就会有明显差距了!

代码

我们可以将数组的第一个值作为”哨兵“,数据存储下标index从1开始,则list的0号位表示暂无元素,位”哨兵“Key。

OC代码

- (NSInteger)searchItemFromArray:(NSArray *)array item:(NSString *)item{
    NSMutableArray *muArray = array.mutableCopy;
    if(muArray == nil || muArray.count <= 0){
        return -1;
    }
    NSInteger index = muArray.count - 1;
    NSString *firstItem = [muArray firstObject];

    if(firstItem == item){
        //如果第一个元素等于查找值,直接返回
        return 0;
    }

    //把要查找的值放在数组的第一位上,作为【标兵】
    muArray[0] = item;
    while (muArray[index] != item) {
        index --;
    }

    //查找结束,把数组的首位元素改回来
    muArray[0] = firstItem;

    return index > 0 ? index : -1;
}

Swift代码

func searchItemFromArray(_ array: Array<String>, item: String) -> NSInteger {
        var array = array
        if array.count == 0{
            return -1
        }
        var index = array.count - 1
        let firstItem = array.first

        if firstItem == item{
            //如果第一个元素等于查找值,直接返回
            return 0
        }

        //把要查找的值放在数组的第一位上,作为【标兵】
        array[0] = item
        while array[index] != item {
            index -= 1
        }

        //查找结束,把数组的首位元素改回来
        array[0] = firstItem!

        return index > 0 ? index : -1
    }

Python代码

def searchItemFromArray(array, item):
    if len(array) == 0:
        return -1

    index = len(array) - 1
    firstItem = array[0]

    if firstItem == item:
        # 如果第一个元素等于查找值,直接返回
        return 0

    # 把要查找的值放在数组的第一位上,作为【标兵】
    array[0] = item
    while array[index] != item:
        index -= 1

    # 查找结束,把数组的首位元素改回来
    array[0] = firstItem

    return index if(index > 0) else -1

结果对比

比如数组中有一千个元素,我查找中间那个元素,运行结果如下:

2019-10-21 20:52:41.415488+0800 OC_DEMO[86929:3800608] 500
2019-10-21 20:52:41.415618+0800 OC_DEMO[86929:3800608] 普通查找耗时: 0.148964 ms

2019-10-21 20:52:41.415716+0800 OC_DEMO[86929:3800608] 500
2019-10-21 20:52:41.415792+0800 OC_DEMO[86929:3800608] 标兵查找耗时: 0.082257 ms

结束语

欢迎各位大神提出宝贵的意见和建议,也欢迎大家进群交流365152048!

CSDN博客 https://zfj1128.blog.csdn.net
GITEE主页 https://gitee.com/zfj1128
GITHUB主页 https://github.com/zfjsyqk