大四时候的一个面试题，当时没想出来，给大家分享一下
题目大意：
有这样一个数组，除其中一个元素（如下面的99），其它的都是成对出现的，如何能快速找出那99的位置
……102，102，2，2，44，44，99，23，23，11，11 ……
[解决办法]
用位操作----异或操作。先全部异或一下得到了99.然后查找99的位置。
[解决办法]
递归+折半查找。
这必须知道数组a的所有值的个数(n+1)，而n+1必为奇数。数组a的序号为0到n。
left = 0; right = n; m = (left+right)/2;
int find99(left,right);
m = (n+0)/2,若m为偶数，也即m两边的数量都为偶数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在左侧，那么接下来就find99(left,m-1)。若与a[m+1]相等，则99必在右侧，那么find99(m+1,right)。若都不相等，则a[m] == 99,return m。
若m为奇数，也即m两边的数量都为奇数，分别判断a[m]与a[m-1]、a[m+1]的值，若与a[m-1]相等，则99必在右侧，find99(m+1,right)。若与a[m+1]相等，则99必在左侧，find99(left,m-1)。若都不相等，则a[m] == 99，return m。
[解决办法]
弄错了，一楼算法的时间复杂度是O（n），二楼的是log（n），但二楼的算法只有当成对的数相邻时才能用。
[解决办法]
#include <iostream>using namespace std;int search_single_num(int *a, int start, int end){ int mid; int start_mid; int end_mid; while(start!=end) { mid = (start+end)/2; if(a[mid]==a[mid-1]) { start_mid = mid; end_mid = mid+1; } if(a[mid]==a[mid+1]) { start_mid = mid-1; end_mid = mid; } if(a[mid]!=a[mid+1] && a[mid]!=a[mid-1]) { return mid; } if((start_mid-start)%2==0) { end = start_mid; } else { start = end_mid; } } return start;}int main(){ int a[11] = {102, 102, 2, 2, 44, 44, 99, 23, 23, 11, 11}; cout<<search_single_num(a, 0, 10)<<endl; return 0;}
[解决办法]
如果发现数组中的99是一定会出现在偶数索引处的话，那么大家是否可以想到一个更加好的解决办法呢？
[解决办法]
void do_find_the_one_diff(int in_data[], size_t len, size_t index){ if (0 == index) { cout << "find the only diff: " << in_data[index] << endl; return; } if (in_data[index - 1] != in_data[index]) { len -= index; in_data += index; } else len = index - 1; index = len >> 1; if (index & 1) ++index; do_find_the_one_diff(in_data, len, index);}void find_the_one_diff(int in_data[], size_t len){ if (len & 1) { size_t index = len >> 1; if (index & 1) ++index; do_find_the_one_diff(in_data, len, index); }}int main(){ int in_data[] = {1, 1, 3, 3, 2, 4, 4, }; size_t len = sizeof in_data / sizeof(int); find_the_one_diff(in_data, len); return 0;}