219. 包含重复 II - 为什么使用二分查找的解决方案适用于未排序的数组？

Question

问题： 给定一个整数数组和一个整数 k，找出数组中是否有两个不同的索引 i 和 j 使得 nums[i] = nums[ j]并且i和j的绝对差值至多为k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true

我用 HashSet(java) 解决了它。

但是当我浏览下面提交的一些解决方案时，有一个引起了我的注意：

 public boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        int len = nums.length;
        
        for(int i=0; i<len; i++) 
        {
            int j = Arrays.binarySearch(nums, nums[i]);// Y this works as array is not sorted. Copied sol from submitted solution
            if(i != j && Math.abs(i-j) <= k) 
            {
                return true;
            }
        }
        
        return false;
    }

输入数组未排序，这也是此代码有效的原因以及它被接受的解决方案。
另外，如果问题是至少而不是最多的差异，如何解决？

Answer 1

您对这个解决方案的正确性有疑问，您是对的。这不是一个合理的算法。如果它通过了测试用例，那只能说明测试还不够彻底。

这是一个反例：

[9, 9, 1, 2, 3]
1

代码将 return false，而它应该 return true。

很明显，如果为了找到 9 而执行二分查找，则不会找到它，因为它会在数组的后半部分查找。

219. 包含重复 II - 为什么使用二分查找的解决方案适用于未排序的数组？

219. Contains Duplicate II - Why solution using binary search works on unsorted array?

arrays

algorithm

binary-search

data-structures