offer_3

//题目1
bool duplicate(int numbers[],int length,int* duplication)
{
  if(numbers == nullptr || length<=0) return false;
  for(int i=0; i<length ;++i){
    if(numbers[i]<0 || num[i]>length-1) return false;
  }
  
  for(int i=0;;i<length;++i){
		while(i != numbers[i]){
			if(numbers[i] == numbers[numbers[i]]){
				*duplication = numbers[i];
				return true;
			}
			int temp=numbers[i];
			number[i]=numbers[temp];
			numbers[temp] = temp;	
		}	
		return false;
	}
}



//题目2
int getDuplication(const int* numbers[],int length)
{
	if(numbers == nullptr || length<=0) return false;
	int start=1;
	int end=length-1;
	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 countRange(int* numbers,int length,int start,int middle)
{
	if(numbers == nullptr) return 0;
	int count=0;
	for(int i=0;i<length;++i){
		if(numbers[i]>=start && numbers[i]<=middle)
			++count;
	}
	return count;
}