面试题三2 题解有问题 about codinginterviewchinese2 HOT 4 CLOSED

题目有要求：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。

from codinginterviewchinese2.

面试题三解法二确实是有问题的，比如针对测试用例

void test11()
{
    int numbers[] = { 0, 1, 2, 0, 4, 5, 6, 7, 8, 9 };
    int duplications[] = { 0 };
    test("test11", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int));
}

mid = 4
然而在[0,4]之间应该有5个数，确实也有5个数。
在[5,9]之间也是应该有5个数，确实有5个数。
您所实现的这个算法在这个样例下的运行结果是：

test11 FAILED.

from codinginterviewchinese2.

@gao-lex 你的数组有问题，数组的长度是10，所以所有的数字应该都在1到9范围内，没有0

from codinginterviewchinese2.

@gao-lex 你的数组有问题，数组的长度是10，所以所有的数字应该都在1到9范围内，没有0

他这个测试用例是leetcode的上的，leetcode的题目是0~n-1范围，就是原题题解是没问题的，但是不能直接套这个题解去解leetcode的题

该题题解无法解决0重复出现应该是因为在
if (count > (mid - start + 1)) end = mid
如果start为0 会导致count = mid
无法正确二分

from codinginterviewchinese2.