[数据结构与算法]剑指offer--不修改数组找出重复的数字（数组长度n+1，数组内数字范围为1~n）二分查找思路

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

按照二分查找的思路，我们把从1～n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1～n。如果1～m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1～n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。
我们以长度为8的数组{2，3，5，4，3，2，6，7}；为例分析查找的过程。根据题目要求，这个长度为8的所有数字都在1～7的范围内。中间的数字4把
1～7的范围分为两段，一段是1～4，另一段是5～7。接下来我们统计1～4这4个数字在数组中出现的次数，它们一共出现了5次，因此这4个数字中一定有重复的数字。
接下来我们再把1～4的范围一分为二，一段是1、2两个数字，另一段是3、4两个数字。数字1或者2在数组中一共出现了两次。我们再统计数字3或者4在数组中出现的次数，它们一共出现了三次。这意味着3、4两个数字中一定有一个重复了。我们再分别统计这两个数字在数组中出现的次数。接着我们发现数字3出现了两次，是一个重复的数字。

#include<iostream>
using namespace std;

int getcount(int* nums,int length,int start,int end){
	if(nums == NULL || length<=0)
		return 0;
	int count = 0;
	for(int i = 0;i < length;i++){
		if(nums[i] >= start && nums[i] <= end)
			count++;
	}
	return count;
}

int getDuplication(int *nums,int length){
	if(nums == NULL || length <= 0)
		return 0;
	int start = 1;
	int end = length - 1;
	while(start <= end){
		int middle = (end-start)/2+start;
		int count = getcount(nums,length,start,middle);
		if(start == end){ //个人觉得写成star == middle;更好理解
			if(count > 1) //但是也正因为start == end; start才等于middle
				return start;
			else
				break;
		}
		if(count > (middle-start)+1)
			end = middle;
		else
			start = middle+1;
	}
	return -1;
}

int main()
{
	int nums[] = {1,2,6,3,6,2,4,7};
	int a = getDuplication(nums,sizeof(nums)/sizeof(int));
	cout<<a<<endl;
	return 0;
}

需要指出的是，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组{2，3，5，4，3，2，6，7}中重复的数字2。这是因为在1～2的范围里有1和2两个数字，这个范围的数字也出现2次，此时我们用该算法不能确定是每个数字各出现一次还是某个数字出现了两次。