算法-哨兵查找法（OC、Swift、Python）

原创

用户6004386

修改于 2019-10-22 10:24:02

1.1K0

修改于 2019-10-22 10:24:02

文章被收录于专栏：iOS代码混淆iOS代码混淆

前言

我们在一个数组中想查找某个对象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(arrayi == item)；但是使用了”哨兵“只有一个判断条件if(arrayi == 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

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

登录后参与评论

0 条评论

热度