3
$\begingroup$

I run across this problem:

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

For example, given [1,2,3,4,5], k=4, x=3, we should have [1,2,3,4]. There is one solution using binary search:

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] <= arr[mid+k] - x)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

I couldn't understand if (x - arr[mid] <= arr[mid+k] - x) part and I try to explain this using precondition, invariant, and postcondition like we do with the simple binary search problem. But, I have no clue what's the invariant in this case and how we prove the invariant holds through the loop execution. I also follow the article from topcoder but that doesn't help.

My attempt for the invariant: the index of the first number that is among the k closest values for the given target is in [left, right]. However, I cannot fully convince myself this is correct and actually holds during the loop.

If this question belongs to stackoverflow, let me know and I'll post it there instead.

Thanks in advance.

$\endgroup$
0
$\begingroup$

The main idea of the algorithm is that mid will indicate the starting point of the subarray of length k that we are interested in (this a bit more specific than your correct intuition about this being in the interval [left,right]).

Notice that x - arr[mid] <= arr[mid+k] - x is equivalent to x <= (arr[mid] + arr[mid+k])/2, which in particular implies that x <= arr[mid+k]. If x-arr[mid] were a negative number, it means that clearly we can move to the left, since x is definitely not in [arr[mid],arr[mid + k]]. So suppose that x - arr[mid] is positive, and suppose for a contradiction that shifting the interval by one to the right gives a better solution: by our conditions and the fact that the array is ordered, we have arr[mid+k+1]-x >= arr[mid+k]-x >= x-arr[mid], which proves that arr[mid+k+1] is further from x than arr[mid] is, a contradiction (notice that we are required to give preference to the smaller elements, so even if the inequalities above were in fact equalities, moving to the right would be a mistake).

This proves that is is safe to set right=mid.

$\endgroup$
  • 1
    $\begingroup$ Thanks for answering. From your explanation I think my invariant statement is correct. However, if we set right = mid, how do we ensure that the interval can cover the starting point of the subarray: the starting point might appear in [mid, x]. Thanks! $\endgroup$ – zack Jun 6 '18 at 14:04
  • $\begingroup$ You are right, my answer needs some major reworking. Thank you for your comment. $\endgroup$ – Leo163 Jun 6 '18 at 14:26
  • $\begingroup$ I corrected it now. $\endgroup$ – Leo163 Jun 6 '18 at 14:46
  • $\begingroup$ Thanks for the update. However, I think your proof still doesn't show right = mid is the safe choice to ensure invariant holds even index of x falls in the interval [mid, mid+k]. From your proof, I can see it is bad move to move right even further right but you haven't shown move right to mid is safe choice. Maybe I misunderstand your statements. $\endgroup$ – zack Jun 6 '18 at 17:49
  • $\begingroup$ It follows from what I wrote: what I did was to show that the interval you are looking for cannot start to the right of mid, hence you can set right=mid (seeing right as the current bound on how to the right the starting point can be). After this stage, if the current position of right is the actual starting point of the solution, only left will be moved to the right, until left=right and the algorithm terminates. $\endgroup$ – Leo163 Jun 7 '18 at 10:21
0
$\begingroup$

If x - arr[mid] <= arr[mid+k] - x, then for any l that l > mid, we have

x - arr[l-1] <= x - a[mid] <= arr[mid+k] - x <= arr[l+k] - x,
arr[l-1] - x <= arr[l+k] - x,

which means |arr[l-1] - x| <= |arr[l+k] - x|. So for any range [l, l+k] where l > mid, we can move it to left until l == mid while the elements contained are no farther from x, therefore it is safe to set right = mid.

Otherwise, the proof is similar.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.