面试题3 数组中的重复数字中不修改原数据的版本有误，比如给定01134567
就无法得出重复数字1，因为这里做二分的时候具有不确定性，也就是count跟end-start+1之间并不是必然联系的。改进版本查找任意一个重复数字的时间复杂度在O(nlogn)到O(nn)之间

// 不修改原数据的改进版本
// 只找一个重复的数据时，时间复杂度在O(nlogn)到O(nn)之间
// 找所有重复就是O(nn)
bool getDupNum3(int* pData, int length)
{
if (pData == NULL || length <= 1)
{
return false;
}
int start = 0;
int end = length - 1;
return innerGetDupNumber(pData, length, start, end);
}

bool innerGetDupNumber(int* pData, int length, int start, int end)
{
int count = countRange(pData, length, start, end);
if (start == end)
{
if (count > 1)
{
printf(“duplicate number %d\n”, start);
return true;
}
return false;
}

int mid = start + ((end - start) >> 1);
if (innerGetDupNumber(pData, length, start, mid))
{
return true;
}
return innerGetDupNumber(pData, length, mid + 1, end);
}