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

Question

Problem: Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

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

I solved it using HashSet(java).

But when I was going through some of the submitted solution below one caught my attention:

 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;
    }

1. Input array isn't sorted then also why this code works and it's accepted solution.
2. Also how to approach it if the problem was difference to be at least instead of at most?

Answer 1

You have doubts about the correctness of this solution, and right you are. It is not a sound algorithm. If it passes the test cases, then that just means the tests are not thorough enough.

Here is a counter example:

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

The code will return false, while it should return true.

It is quite obvious that if a binary search is performed in order to find a 9, it will not be found, since it will look in the second half of the array.