2019-11-02 吴亲库里 库里的深夜食堂
题目让我们找出重复的数，给定的数组的值都在1-n之间，数组总数是n+1,那么必然有数字是重复的，让我们来找出这个重复的数。
****
这道题可以有更好的解法(我这里强行把它当做二分的场景)，二分的解题思路就是取n的中位数，遍历数组，统计不大于中位数的个数，如果不大于中位数的个数比中位数还大，说明重复的数在中位数的左边(注意包括中位数自己，理解一下这一句)，否则的话重复的数肯定出现在中位数的右边，而且肯定不包括中位数。好了下面看代码再细讲。
/**
* @param Integer[] $nums
* @return Integer
*/
function findDuplicate($nums) {
$left = 1;
$right = count($nums) - 1;
while ($left < $right) { // <
$middle = ($left + $right) >> 1;
$sum = 0;
for ($j = 0; $j < count($nums); $j++) {
if ($nums[$j] <= $middle) {
$sum++;
}
}
if ($sum <= $middle) { //排除掉中位数
$left = $middle + 1;
} else { //不能排除中位数
$right = $middle;
}
}
//相返回left还是right都可以 因为必然存在left==right
return $left;
}
