Java Binary Search Easy to Understand 5ms
\nclass Solution {\n    /**\n\t * The idea is to perform binary search over the array and find the element\n\t * if it exists, otherwise we find the closest ele
```\nclass Solution {\n    /**\n\t * The idea is to perform binary search over the array and find the element\n\t * if it exists, otherwise we find the closest element and we return its index\n\t * \n\t * once we have the index we\'ll have two pointers to look for closest elements\n\t * both left and right\n\t */\n\tpublic List<Integer> findClosestElements(final int[] arr, int k, int x) {\n\n\t\t/* we use a LinkedList because we need to return our answer list sorted */\n\t\tfinal LinkedList<Integer> result = new LinkedList<>();\n\t\tfinal int index = binarySearch(arr, x);\n\n\t\t/*\n\t\t * we create two pointers to expand from center, decrementing left and\n\t\t * incrementing right\n\t\t */\n\t\tint left = index;\n\t\tint right = index + 1;\n\n\t\twhile (k-- > 0) {\n\t\t\t/* we look at both sides to find the closest */\n\t\t\tint leftDiff = left >= 0 ? Math.abs(x - arr[left]) : Integer.MAX_VALUE;\n\t\t\tint rightDiff = right < arr.length ? Math.abs(x - arr[right]) : Integer.MAX_VALUE;\n\n\t\t\t/* to keep the list sorted, if we find closest on the left we add it to front */\n\t\t\tif (leftDiff <= rightDiff) {\n\t\t\t\tresult.addFirst(arr[left--]);\n\t\t\t} else {\n\t\t\t\t/* if the closest is on the right we add it to the end */\n\t\t\t\tresult.add(arr[right++]);\n\t\t\t}\n\t\t}\n\n\t\treturn result;\n\t}\n\t\n\tprivate int binarySearch(final int[] arr, int x) {\n\n\t\t/* check if x is smaller than the first element */\n\t\tif (x < arr[0]) {\n\t\t\treturn 0;\n\t\t}\n\n\t\t/* check if x is greater than the last element */\n\t\tif (x > arr[arr.length - 1]) {\n\t\t\treturn arr.length - 1;\n\t\t}\n\n\t\tint low = 0;\n\t\tint high = arr.length - 1;\n\n\t\twhile (low <= high) {\n\t\t\t/* we do it this way to avoid integer over flow */\n\t\t\tint mid = low + (high - low) / 2;\n\n\t\t\tif (arr[mid] < x) {\n\t\t\t\tlow = mid + 1;\n\t\t\t} else if (arr[mid] > x) {\n\t\t\t\thigh = mid - 1;\n\t\t\t} else {\n\t\t\t\treturn mid;\n\t\t\t}\n\t\t}\n\n\t\t/*\n\t\t * we come here when the element is not in the array so we look for the closest\n\t\t * element to it, and right now our low and high both should be closer but we\n\t\t * need to find the closest\n\t\t */\n\t\tif (Math.abs(x - arr[low]) < Math.abs(x - arr[high])) {\n\t\t\treturn low;\n\t\t} else {\n\t\t\treturn high;\n\t\t}\n\n\t}\n}\n```
[]