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

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

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

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

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

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

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

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

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

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

顺序查找

#include <stdio.h>

#include <stdlib.h>

#define MAX_LENGTH 100typedef int KeyType

typedef struct {

KeyType *elem

int length

}SSTable //顺序表的存储结构

int Search_Seq(SSTable ST, KeyType key){

int i

ST.elem[0] = key //“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必定指向该哨兵

for(i = ST.lengthST.elem[i] != keyi--)

return i //找到的话，则i != 0,否则i = 0

}

void main()

{

int i, key

SSTable T

T.elem = (KeyType *)malloc(sizeof(KeyType))

printf("How Many Entries Do You Want input\n")

scanf("%d", &T.length)

for(i=1i<=T.lengthi++){

printf("Please input the %dth entries \n", i)

scanf("%d", &T.elem[i])

}

for (i=1i<=T.lengthi++)

printf("%5d",T.elem[i])//显示已经输入的所有数据

printf("\nPlease input the data you want to search\n")

scanf("%d", &key)

i = Search_Seq(T,key)

printf("the search data is locate the %dth(0 indicate can not find)\n",i)

}

折半查找

#include <stdio.h>

#include <stdlib.h>

int binSearch(const int *Array,int start,int end,int key)

{

int left,right

int mid

left=start

right=end

while (left<=right) {

mid=(left+right)/2

if (key<Array[mid])

{

right=mid-1

}

else if(key>Array[mid])

{

left=mid+1

}

else

return mid

}

return -1

}

void main()

{

int A[]={10,20,30,40,50,60,70,80}

int n

printf("Please search num:")

scanf("%d",&n)

int index=binSearch(A,0,8,n)

if(index==-1)

{

printf("no num")

}

else

{

printf("index=%d",index+1)

}

}

所谓“哨兵”就是用一个特殊值来作为数组的边界，使用“哨兵”可以少用一条判断语句，所以可以提高程序的效率。

比如从整数数组arr中，查找有没有整数num。

应用：假设一个乱序数组，需要查找一个元素是否在该数组中，这时需要用到顺序查找，也就是遍历数组。

一般情况下我们会写下如下代码：

int Sequential_Search(int *a,int n,int key)

{

//数组从1开始

int i

for(int i=1i<=ni++)

{

if(a[i]==key)

return i

}

return 0//查找失败

}

有的数据结构书上，会运用哨兵元素，改成这样的代码：

int Sequential_Search2(int *a int n,int key)

{

int i=0

a[0]=key//哨兵

i=n

while(a[i]!=key)

{

i--

}

return i//返回0就是查找失败

}

---