一个长度为n + 1的数组里面的所有数字都在1 ~ n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{7,7,5,4,2,6,1,3}，那么对应输出的应该是7。

1，官方解答

/*先将元素划分为两部分，计算前面部分的元素在整个数组中出现的次数，如果出现次数大于元素个数，
*则重复数字在这一部分，否则在另一部分，重复以上步骤即可*/ 
#include <iostream>
using namespace std;
#define nullptr NULL 

int countRange(const int *numbers,int length,int start,int end){
    if(numbers == nullptr)
        return 0;
    int count = 0;
    
    for(int i = 0;i < length;i++){
    //计算在[start,end]之间的元素在整个数组内的出现次数
        if(numbers[i] >= start && numbers[i] <= end)         
            ++count;
    }
    return count;
}


int GetDuplication(const int *numbers,int length){        
    if(numbers == nullptr || length <= 0)
        return -1;
     
    int start = 1;       //题目限定范围为1 ~ n，所以划分的时候起始位置为1
    int end = length - 1;            
    //所以start和end在这里并不是作为数组下标，而是作为划分的起始和结束位置
    while(end >= start){
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers,length,start,middle); //获得元素出现次数之和
        
        if(end == start){
            if(count > 1)
                return start;
            else
                break;
        }
        //当前划分含有重复数字时，下一个循环就是对该划分进行二次划分
        if(count > (middle- start + 1))    
            end = middle;
        else start = middle + 1;   //否则就对另一个划分进行二次划分
    }
    return -1;
}


int main(){
    int array[8] = {7,7,5,4,2,6,1,3};
    cout<<GetDuplication(array,8);
    return 0;
}