java - 为什么在二分查找中返回低位而不是高位？

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:

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

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

3. 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])查看数组，可能会发生两种情况:

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

这是正确的，因为其他一些元素可以重命名到该组中，但不能重命名出来。在这种情况下，预期的元素数量是 [3, 4]，但是我们有一个额外的 4(作为重复项)，然后重命名了两个 4，这就是为什么我们有 5。

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

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

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

不清楚为什么你认为你必须返回low而不是high 。我怀疑您没有使用多种不同类型的输入对此进行测试。对于输入1,1,2，高位和低位都会为0。是否返回high或low ，答案将是错误的。

换句话说:

• 实现没有正确解决问题，给出了错误的结果
• “回答谎言还是高调”这个问题是错误的问题

你的算法的解释听起来很正确。问题是，你还没有真正实现你在那里解释的内容。您谈论了对范围内的元素进行计数，并随时调整范围的下限和上限，但在您的实现中，您计算​​ nums[I] <= mid ，所以只有上限发生变化( mid )，下限始终(隐式)0。这与您的解释不符。你没有正确实现你的想法。