算法-哨兵查找法（OC、Swift、Python）
原创
在这里插入图片描述
前言
我们在一个数组中想查找某个对象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 删除。
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
数据保险箱
数据保险箱（Cloud Data Coffer Service，CDCS）为您提供更高安全系数的企业核心数据存储服务。您可以通过自定义过期天数的方法删除数据，避免误删带来的损害，还可以将数据跨地域存储，防止一些不可抗因素导致的数据丢失。数据保险箱支持通过控制台、API 等多样化方式快速简单接入，实现海量数据的存储管理。您可以使用数据保险箱对文件数据进行上传、下载，最终实现数据的安全存储和提取。
腾讯云开发者
