Invariant on "Find K Closest Elements" problem 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&lt;int&gt; findClosestElements(vector&lt;int&gt;&amp; arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    while (left &lt; right)
    {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] &lt;= arr[mid+k] - x)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return vector&lt;int&gt;(arr.begin() + left, arr.begin() + left + k);
}


I couldn't understand if (x - arr[mid] &lt;= 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.
If x - arr[mid] &lt;= arr[mid+k] - x, then for any l that l &gt; mid, we have

x - arr[l-1] &lt;= x - a[mid] &lt;= arr[mid+k] - x &lt;= arr[l+k] - x,
arr[l-1] - x &lt;= arr[l+k] - x,


which means |arr[l-1] - x| &lt;= |arr[l+k] - x|. So for any range [l, l+k] where l &gt; 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.