题目：在一个长度为n+1的数组中，所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
1.同样可以用O（n）的空间复杂度，用哈希方法
2.把1-n的数字从中间的数字m分为两部分，前面一半为1-m，后面一半为m+1-n。如果1-m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1-n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法类似。
剑指offer代码：（因为数字是1-n所以start=1，end=length-1 >>1右移1位除以2 数出来结果还要判断一下现在是还是一个区间还是已经只是一个单独的数字了的情况）
原文：https://www.cnblogs.com/libin123/p/12751346.html