CODEWITHSUNDEEP
java
Wizard
Wizard

Reputation: 22123

Binary search to Find K Closest Elements of an array

I am learning binary search in leetcode from problem Find K Closest Elements - LeetCode

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.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

It's official solution:

Approach 2: Binary Search and Two Pointers

Algorithm

The original array has been sorted so we can take this advantage by the following steps.

  1. If the target x is less or equal than the first element in the sorted array, the first k elements are the result.

  2. Similarly, if the target x is more or equal than the last element in the sorted array, the last k elements are the result.

  3. Otherwise, we can use binary search to find the index of the element, which is equal (when this list has x) or a little bit larger than x (when this list does not have it). Then set low to its left k-1 position, and high to the right k-1 position of this index as a start. The desired k numbers must in this rang [index-k-1, index+k-1]. So we can shrink this range to get the result using the following rules.

    • If low reaches the lowest index 0 or the low element is closer to x than the high element, decrease the highindex.

    • If high reaches to the highest index arr.size()-1 or it is nearer to x than the low element, increase the lowindex.

    • The looping ends when there are exactly k elements in [low, high], the subList of which is the result.

The implementation

public class Solution {
    public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
        int n = arr.size();
        if (x <= arr.get(0)) {
            return arr.subList(0, k);
        } else if (arr.get(n - 1) <= x) {
            return arr.subList(n - k, n);
        } else {
            int index = Collections.binarySearch(arr, x);
            if (index < 0)
                index = -index - 1;
            int low = Math.max(0, index - k - 1), high = Math.min(arr.size() - 1, index + k - 1); #1????

            while (high - low > k - 1) {
                if (low < 0 || (x - arr.get(low)) <= (arr.get(high) - x)) #2????
                    high--;
                else if (high > arr.size() - 1 || (x - arr.get(low)) > (arr.get(high) - x)) #????
                    low++;
                else
                    System.out.println("unhandled case: " + low + " " + high);
            }
            return arr.subList(low, high + 1);
        }
    }
}

I have 3 questions about the implementation

  1. low = Math.max(0, index - k - 1), I assumed it as low = Math.max(0, index - k - 1), since low's left position is [index -k +1]not [index-k-1].
  2. if (low < 0 || (x - arr.get(low)) <= (arr.get(high) - x)) #2????, since low was set as low = Math.max(0, index - k - 1), and it will increase forwards, is it necessary to check low < 0, the same as else if (high > arr.size() - 1 || (x - arr.get(low)) > (arr.get(high) - x)) #????
  3. while (high - low > k - 1), what's the benefit of it over high - low >=k?

Upvotes: 2

Views: 2843

Answers (1)

recnac
recnac

Reputation: 3744

First I want to say, it is the lowest quality official solution I read in Leetcode, as you said, it indeed has many defect in this solution. I will explain it one by one.

For Question1:
you are kind of correct here, we should change Math.max(0, index - k - 1) to Math.max(0, index - k) but not Math.max(0, index - k + 1). because when the target number x is not in array and left k is the result we want, we should start from index - k.
for example:
Input: [1,2,3,10,11], k=4, x=2
index is 3, and we should start from index-k=2

For Question2:
you are correct, low < 0 and high > arr.size() - 1 are unnecessary check here. you can just remove it.

For Question3:
high - low > k - 1 is equals to high - low >= k in integer comparison. These are just two different programming habits, choose the one you like.

Hope that helps you, and comment if you have further questions. : )

Upvotes: 2

Related Questions