前言
當看到題目是在一個數組中查找某一個元素，或是在一個字符串中查找某個字符，我們一般都會寫出如下代碼。但這樣的代碼雖然簡潔明了，但在數組元素很多的情況下，并不是一個很好的解決方案，今天我就來分享一個提高查找速度的小技巧.
//在一個int數組中查找某個元素int find(int A[],int n,int element){ for( int i = 0; i < n; i++ ) { if( A[i] == element ) return i; } return -1;}//在一個字符串中查找某個字符int find(string& str,char c){ for( int i = 0; i < str.length(); i++ ) { if( str[i] == c ) return i; } return -1;}雖然每次都是寫出這樣的代碼，但我總覺得for循環中的<判斷有點多余，比如數組中有100個元素，我們明明知道前99個是不會數組越界的，根本不需要判斷i<n的，但我們卻多判斷了99次，昨天晚上看編程珠璣的時候發現了這個小技巧，今天就來分享一下。
通過哨兵的方式去掉這多余的判斷，將上面兩個方法改造如下：
//在一個int數組中查找某個元素int find1(int A[],int n,int element){ if( n <= 0 ) return -1; if( A[--n] == element ) return n; int hold = A[n]; A[n] = element; int i = 0; for( ; ; i++ ) { if( A[i] == element ) break; } A[n] = hold; return i < n ? i : -1; }//在一個字符串中查找某個字符int find1(string& str,char c){ int n = str.length(); if( n <= 0 ) return -1; if( str[--n] == c ) return n; int hold = str[n]; str[n] = c; int i = 0; for( ; ; i++ ) { if( str[i] == c ) break; } str[n] = hold; return i < n ? i : -1; }我勒個去，怎么變得這么長，但的確是減少了判斷的次數，如果數組較大的話提高運行速度肯定是一定的，如果你非要說數組很小的話，說不定速度還要降低呢，那你不這樣寫不就得了，好了廢話少說，雖然代碼已經很簡單明了了，但我還是簡單說一下思路。
就是在數組的末尾加一個哨兵，即使不判斷i<n也能確保數組不越界，加了哨兵之后if語句是必然會break的。
先判斷最后一個元素的值是不是我們要查找的數，如果是，返回其下標；如果不是，將最后一個數的值保存起來，將要查找的那個數賦給最后一個元素，循環查找指定的元素，不用判斷數組越界，if語句必然break，將最后一個元素的值還原，最后只用判斷i<n，如果是i即為所求，否則要查找的元素不在數組中。
最后在做一個簡單的性能測試，看到底能否提高查找速度。
測試代碼如下：
void testFind(){ int N = 200000; int* A = new int[N]; A[N-2] = 1; DWORD start = ::GetTickCount64(); for( int i = 0; i < 10000; i++ ) find(A,N,1); DWORD end = ::GetTickCount64(); cout <<"優化前：" << end - start <<" 毫秒" << endl; start = ::GetTickCount64(); for( int i = 0; i < 10000; i++ ) find1(A,N,1); end = ::GetTickCount64(); cout <<"優化后：" << end - start <<" 毫秒" << endl; }運行結果如下：
速度還是會快一點
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
新聞熱點
疑難解答
