Java | O(logN + k) | Intuitive | binary search, 2 pointers
2 Steps:\n1. Binary search to find index of first element in array that is >= target number x. O(logN).\n2. Initialize left and right pointers around this index
**2 Steps:**\n1. Binary search to find index of first element in array that is >= target number x. **O(logN)**.\n2. Initialize left and right pointers around this index. Expand k elements from this center by adding (left or right) elements to the list depending on which is closer. **O(k)**.\n**Note** -  While adding right element, append at end of list, and while adding left, insert at beginning of list, so that the final list is always sorted. We use a linked list to ensure these operations are O(1) each.\n\n`Code for Step 1:`\n```\n// Binary Search - returns index of first number >= x in array arr\nprivate int search(int[] arr, int x) {\n\tif(arr.length==0 || x<arr[0]) return 0;\n\tif(x>arr[arr.length-1]) return arr.length;\n\tint left=0;\n\tint right=arr.length-1;\n\twhile(left<right) {\n\t\tint mid = left + (right-left)/2;\n\t\tif (x==arr[mid]) return mid;\n\t\tif (x>arr[mid]) left = mid+1;\n\t\telse right = mid;\n\t}\n\treturn left;\n}\n```\n`Code for Step 2:`\n\n```\npublic List<Integer> findClosestElements(int[] arr, int k, int x) {\n\tLinkedList<Integer> list = new LinkedList<>();\n\tint right = search(arr, x); // arr[right] >= x;\n\tint left = right-1; // arr[left] < x\n\twhile(k>0) {\n\t\tif      (left<0)                        list.addLast(arr[right++]); // left bound reached\n\t\telse if (right>=arr.length)             list.addFirst(arr[left--]); // right bound reached\n\t\telse if (arr[right]-x < x-arr[left])    list.addLast(arr[right++]); // right is closer\n\t\telse                                    list.addFirst(arr[left--]); // left is closer\n\t\tk--;\n\t} \n\treturn list;\n}\n```
[]