<p>Given a <strong>sorted</strong> integer array <code>arr</code>, two integers <code>k</code> and <code>x</code>, return the <code>k</code> closest integers to <code>x</code> in the array. The result should also be sorted in ascending order.</p>

<p>An integer <code>a</code> is closer to <code>x</code> than an integer <code>b</code> if:</p>

<ul>
	<li><code>|a - x| &lt; |b - x|</code>, or</li>
	<li><code>|a - x| == |b - x|</code> and <code>a &lt; b</code></li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> arr = [1,2,3,4,5], k = 4, x = 3
<strong>Output:</strong> [1,2,3,4]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> arr = [1,2,3,4,5], k = 4, x = -1
<strong>Output:</strong> [1,2,3,4]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= arr.length</code></li>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>
	<li><code>arr</code> is sorted in <strong>ascending</strong> order.</li>
	<li><code>-10<sup>4</sup> &lt;= arr[i], x &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size()-1;
        int index = -1;
        while (left + 1 < right)
        {
            int mid = left + (right-left)/2;
            if (arr[mid] == x)
            {
                index = mid;
                break;
            }
            else if (arr[mid] > x)
                right = mid;
            else
                left = mid;
        }
        if (index == -1)
            index = abs(arr[left] - x) > abs(arr[right] - x) ? right : left;
        
        list<int> result;
        result.push_back(arr[index]);
        left = right = index;
        int cnt = 1;
        while (cnt < k && left > 0 && right < arr.size()-1)
        {
            if (abs(arr[left-1] - x) > abs(arr[right+1] - x))
            {
                right++;
                result.push_back(arr[right]);
            }
            else
            {
                left--;
                result.push_front(arr[left]);
            }
            cnt++;
        }
        
        if (left == 0)
        {
            for (int i = cnt; i < k; i++)
                result.push_back(arr[++right]);
        }
        else
        {
            for (int i = cnt; i < k; i++)
                result.push_front(arr[--left]);
        }
        
        vector<int> v_result;
        for (auto x : result)
            v_result.push_back(x);
        
        return v_result;
        
        
        /*
        if (k == arr.size())
            return arr;
        int left = 0;
        int right = arr.size()-1;
        int index = -1;
        bool flag = true;
        while (left < right)
        {
            int mid = left + (right-left)/2;
            cout << left << " " << mid << " " << right << endl;
            if (arr[mid] == x)
            {
                index = mid;
                flag = false;
                break;
            }
            else if (arr[mid] < x)
                left = mid + 1;
            else
                right = mid - 1;
        }
        
        if (flag)
        {
            if (arr[left] == x)
                index = left;
            else if (arr[left] < x)
                index = min(left+1, int(arr.size())-1);
            else
                index = max(0, left-1);
        }
        
        cout << "index " << index << endl;
        int ll = max(0, index-k+1);
        int rr = min(int(arr.size())-1, index+k-1);
        int lr = index, rl = index;
        
        
        while (ll + 1 < lr && rl + 1 < rr)
        {
            int lmid = ll + (lr-ll)/2;
            int rmid = rl + (rr-rl)/2;
            cout << ll << " " << lmid << " " << lr << ", " << rl << " " << rmid << " " << rr << endl;
            if (arr[lmid] - x < arr[rmid] - x)
            {
                if (lmid + rmid + 2 < k)
                    lr = lmid;
                else
                    rr = rmid;
            }
            else
            {
                if (lmid + rmid + 2 < k)
                    rl = rmid;
                else
                    ll = lmid;
            }
        }
        
        int p1 = 0;
        int p2 = 0;
        if (ll + 1 == lr)
        {
            p1 = lr;
            p2 = index + k-(index - lr + 1);
            if (arr[p1-1]-x < arr[p2]-x)
            {
                p1--;
                p2--;
            }
        }
        else if (rl + 1 == rr)
        {
            p2 = rl;
            p1 = index - (k-(rl - index + 1));
            if (arr[p2+1]-x < arr[p1]-x)
            {
                p2++;
                p1++;
            }
        }
        
        vector<int> result;
        for (int i = p1; i <= p2; i++)
            result.push_back(arr[i]);
        return result;
        */
        
    }
};
40000