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

image

前言

我们在一个数组中想查找某个对象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