面试题 3.2：不修改数组找出重复的数字

03_02_FindDuplicationNoEdit.cpp

int getDuplication(const int *numbers, int length) {
    if(numbers == nullptr || length <= 0) {
        return -1;
    }
    int start = 1;
    int end = length-1;
    while(end >= start) {
        int middle = ((end - start) >> 1) + start;
        int count = countRange(numbers, length, start, middle);
        if(count > (middle - start + 1)) {
            end = middle;
        }
        else {
            start = middle + 1;
        }
        if(end == start) {
            if(count > 1) {
                return start;
            }
            else {
                break;
            }
        }
    }
    return -1;
}

int countRange(const int *numbers, int length, int start, int end) {
    if(numbers == nullptr) {
        retun 0;
    }
    int count = 0;
    for(int i = 0; i < length; i++) {
        if(numbers[i] >= start && numbers[i] <= end) {
            ++count;
        }
    }
    return count;
}