在一个数组中查找某一个元素，或是在一个字符串中查找某个字符，我们一般都会写出如下代码。这样的代码虽然简洁明了，但在数组元素很多的情况下，并不是一个很好的解决方案，今天我就来分享一个提高查找速度的小技巧.
//在一个int数组中查找某个元素
intfind(intA[],intn,intelement)
{
for(inti=0;i<n;i++)
{
if(A[i]==element)
returni;
}
return-1;
}
//在一个字符串中查找某个字符
intfind(string&str,charc)
{
for(inti=0;i<str.length();i++)
{
if(str[i]==c)
returni;
}
return-1;
}
虽然每次都是写出这样的代码，但我总觉得for循环中的，昨天晚上看编程珠玑的时候发现了这个小技巧，今天就来分享一下。
通过哨兵的方式去掉这多余的判断，将上面两个方法改造如下：
//在一个int数组中查找某个元素
intfind1(intA[],intn,intelement)
{
if(n<=0)
return-1;
if(A[--n]==element)
returnn;
inthold=A[n];
A[n]=element;
inti=0;
for(;;i++)
{
if(A[i]==element)
break;
}
A[n]=hold;
returni<n?i:-1;
}
//在一个字符串中查找某个字符
intfind1(string&str,charc)
{
intn=str.length();
if(n<=0)
return-1;
if(str[--n]==c)
returnn;
inthold=str[n];
str[n]=c;
inti=0;
for(;;i++)
{
if(str[i]==c)
break;
}
str[n]=hold;
returni<n?i:-1;
}
我勒个去，怎么变得这么长，但的确是减少了判断的次数，如果数组较大的话提高运行速度肯定是一定的，如果你非要说数组很小的话，说不定速度还要降低呢，那你不这样写不就得了，好了废话少说，虽然代码已经很简单明了了，但我还是简单说一下思路。
就是在数组的末尾加一个哨兵，即使不判断i也能确保数组不越界，加了哨兵之后if语句是必然会break的。
先判断最后一个元素的值是不是我们要查找的数，如果是，返回其下标；如果不是，将最后一个数的值保存起来，将要查找的那个数赋给最后一个元素，循环查找指定的元素，不用判断数组越界，if语句必然break，将最后一个元素的值还原，最后只用判断i，如果是i即为所求，否则要查找的元素不在数组中。
最后在做一个简单的性能测试，看到底能否提高查找速度。
测试代码如下：
voidtestFind()
{
intN=200000;
int*A=newint[N];
A[N-2]=1;
DWORD start=::GetTickCount64();
for(inti=0;i<10000;i++)
find(A,N,1);
DWORD end=::GetTickCount64();
cout<<"优化前："<<end-start<<" 毫秒"<<endl;
start=::GetTickCount64();
for(inti=0;i<10000;i++)
find1(A,N,1);
end=::GetTickCount64();
cout<<"优化后："<<end-start<<" 毫秒"<<endl;
}
运行结果如下：
速度还是会快一点
畅学电子
