Come on in! Give the best binary search rule explanation without magic!
I saw most of posts using binary search did not give fairly convincing explanation about the binary search rule. So I have to make one so that everyone does not
I saw most of posts using binary search did not give fairly convincing explanation about the binary search rule. So I have to make one so that everyone does not have trouble to understand. Also they also secretly combine some cases together(I can see 4 "if else" conditions are merged to 2, very sad to see! **No tricks, readable has always been my priciple...**)\n\nKeywords: **Binary Search, Sliding Window**\n\n---\n**Logic**\nBack to the point, the logic is that we can use binary search to find the left bound of k closest elements. Left bound index ranges from `0` to `n - k` where `n` is the total number of elements in `arr`. Otherwise if left bound index is greater than `n - k`, we will run out of elements to make up k elements in result. Then how to find the left bound index which can gives you k closest elements?\n**Do Binary search in range `[0, n - k]`**\n![image](https://assets.leetcode.com/users/images/697378d4-f75e-4604-9bd5-24a3ffbeefa0_1642538012.818219.png)\n\n\n\nWe will have a `mid` as left bound candidate, and all k elements are in range of `arr[mid, mid + k - 1]`. The the **most important part** is here: we are checking if all the curent k elements move 1 step right, whether we can achieve the **closer** k elements or not. Since 1 step right, **we are throwing `arr[mid]`, and add `arr[mid + k]` into the team, and other middle elements they keep staying**. That is to say, we only need to care if `arr[mid + k]` can be a better man than `arr[mid]` in the current k elements. If so, we move left bound index: `mid`, or all current sliding window with size k 1 step right. Otherwise, search in the left of `arr[mid + k]`, because the right of `mid + k` will only gives us worse result. \n\nTherefore, 4 cases comes to us, please check below image along with code with inline comments.\n\n![image](https://assets.leetcode.com/users/images/63c38b00-552f-481e-a5c1-e505e6c00f47_1642153497.5391467.png)\n\n---\n**Duplicates Handled ? !**\n(If you never think about duplicate, you only solved this problem half...)\nYes! You may have seen similar problems in leetcode before: **[272. Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)**. The difference between them is not only this problem input is array, the other is Binary Search Tree, but also, **this problem can cantains duplicates. but lc 272 does not have duplicates(properties of BST)**. \n\n**How it can cause issues or complexity for having duplicates ?**\n**Because we cannot shrink the search space on same cases where we meet duplicates!(Shrink Search Space is the key of Binary Search, right?)**\nWhen we have duplicate, and say `mid` and `mid + k` are the same, 3 cases for them:\n1. Both `mid` and `mid+ k` are on left side of x, e.g.\n\t```\n\tindex   0   1   2   3   4   5   6   7   8   9  10   11   12\n\t\t\t1   2   2   2   2   2   2   2   2   2   2    3    3\n\t\t\t\t\t\t\tm              m+k   \t\t x\n\t```\n2. Both `mid` and `mid+ k` are on right side of x, (example not added)\n3. `mid` is on left of `x` and `mid+ K` is in right side of x(example not added)\n\nFor above 3 cases:\n- Case 1: if we **move right**, we might get closer `k` elements\n- Case 2: if we **move left**, we might get closer `k` elements\n- Case 3: we **do not have move**, we already find the closest k elements. (Move 1 step right will give as equally closest k elements)\n\nOur code already handle it properly :)\n\n---\n**Final Code**\n```java\nclass Solution {\n    public List<Integer> findClosestElements(int[] arr, int k, int x) {\n        // find the left bound of k elements using binary search\n        int left = 0;\n        int right = arr.length - k; // the biggest index of left bound\n        while(left < right){\n            int mid = left + (right - left)/2;\n            // if mid is to the right of x, then move right will push elements away, so do not move right => right = mid;\n            if(x <= arr[mid]) right = mid; \n            \n            // if mid + k is on the left side of x, then mid + k is closer than mid for sure, so mid + 1 is a better left bound which can remove futher \n            // element: mid, and introduce a closer element: mid + k\n            else if(x >= arr[mid + k]) left = mid + 1; \n            \n            // if mid and mid + k are on both sides of x, then we are choose between mid and mid + k \n            // mid is closer than mid + k, move right will lose a closer one element: mid, and a futher one element: mid + k, so\n            // do not move right => right = mid\n            else if(x - arr[mid] <= arr[mid + k] - x) right = mid;\n            \n            // mid + k is closer one than mid, so mid + 1 is a better left bound, move 1 step right, \n            // remove a futher element: mid, and introduce a new closer element: mid + k\n            else left = mid + 1;  \n        }\n        \n        // add k elements from left to result\n        List<Integer> res = new ArrayList<>();\n        for(int i = left; i < left + k; i++){\n            res.add(arr[i]);\n        }\n        \n        return res;\n    }\n}\n```\n\n---\n**Duplicate Afterwords**\nBut there is another way to handle it by without purely using absolute distance, as follows(you can find it in most top posts, but I am not really a fan of it. At least the posts should make properly explanation about the induction rule in Binary Search, at least should mention Sliding Window as we are considering the k elements in window as a whole, not just comparing the `arr[mid]` and `arr[mid + k]` which is too superficial...):\n\n```java\npublic List<Integer> findClosestElements(int[] A, int k, int x) {\n        int left = 0, right = A.length - k;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (x - A[mid] > A[mid + k] - x) // not using absolute difference to handle above 3 cases for duplicates\n                left = mid + 1;\n            else\n                right = mid;\n        }\n        return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());\n    }\n```
[]