为什么在这个二进制搜索中 return 低，而不是高？

Question

Given an unsorted array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).

You must use only constant, O(1) extra space.

There is only one duplicate number in the array, but it could be repeated more than once.

对于注释1，我们不能对数组进行排序，对于注释2，我们不能使用散列。我想我们可以在这里使用二进制搜索。

假设我们有这个包含重复数字 4 的数组：

[1, 4(was 2), 3, 4, 5, 6, 4(was 7), 8, 9, 4]

想法是我们通过范围过滤器（如 [7,9]）查看数组，可能会发生 2 种情况：

情况一：范围包含重复的元素，在这种情况下，我们在过滤器中可以找到的元素数必须大于它应该有的元素数。例如，如果我们查看 [3, 4]，我们将找到 5 个元素。如果没有重复出现，应该只有两个 [3, 4].

这是真的，因为一些其他元素可以重命名到这个组中，但不能重命名出来。在这种情况下，元素的预期数量是 [3, 4]，但我们有一个额外的 4（作为副本），然后两个 4 重命名，这就是为什么我们有 5.

情况2：范围不包含重复元素，在这种情况下，我们在过滤器中可以找到的元素数必须等于或小于元素数。

下面是我的更新代码。我不确定最后一行 return 是哪一个。虽然我测试发现低是正确的，但我仍然不知道原因。

public int findDuplicate(int[] nums) {
    int low = 1, high = nums.length - 1;
    while(low <= high){
        int mid = low + (high - low) / 2;
        int count = 0;
       //count the number of elements in the filter [low,mid]
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= mid && nums[i]>=low){
                count++;
            }
        }
        if(count > mid-low+1){  //the duplicate would be in the left half
            high = mid;
        } else {          //the duplicate would be in the right half
            low = mid + 1;
        }
    }
    return low; // Why we should return low here, not high?
}

Answer 1

不清楚为什么您认为必须 return low 而不是 high。我怀疑您没有使用许多不同类型的输入对此进行测试。对于输入1,1,2，high和low都会为0。无论你returnhigh还是low，答案都是不正确的。

换句话说：

实施没有正确解决问题，给出了不正确的结果
问题 "to return lie or high" 是一个错误的问题

您对算法的解释听起来不错。问题是，您实际上并没有实施您在那里解释的内容。你谈到计算一个范围内的元素，随你调整范围的下限和上限，但在你的实现中，你计算 nums[I] <= mid，所以只有上限改变（mid），下限始终（隐含地）为 0。这与您的解释不符。你没有正确实现你的想法。

为什么在这个二进制搜索中 return 低，而不是高？

Why to return low, but not high in this binary search?

java

arrays

duplicates

binary-search