CODEWITHSUNDEEP
javaalgorithmbinary-search
user3036345
user3036345

Reputation: 1

Binary Search: Nearest K Elements

I tried to solve the "find nearest K elements in a sorted array" problem of Leetcode using binary search approach but unable to figure out why its not working.

LeetCode Problem Link: text

Problem Description:

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

An integer a is closer to x than an integer b if:

Example 1:

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

Output: [1,2,3,4]

Tried writing the program to solve K nearest numbers in a sorted array:

The program make sure that it never overwrite the best solution found so far by introducing minimumDiff variable:

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int startIndex = 0;
        int low = 0;
        int high = arr.length - k;
        int mid = -1;
        int minimumDiff = Integer.MAX_VALUE;
        int diff = 0;
        while(low <= high) {
            mid = low + (high - low)/2;
            if((mid + k  arr.length) || (x - arr[mid] > arr[mid + k] - x)) {
                low = mid + 1;
                diff = x - arr[mid];
            }else {
                high = mid - 1;
                diff = arr[mid + k] - x;
            }
            if(minimumDiff > diff) {
                minimumDiff = diff;
                startIndex = mid;
            }
        }
        List<Integer> nearestKElements = new ArrayList<>();
        for(int i=startIndex; i<startIndex+k; i++){
            nearestKElements.add(arr[i]);
        }
        return nearestKElements;
}

However it still fails for input:

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

Output: [4,4,4]

Expected Output: [2, 3, 4]

Questions:

1.Can you please help me know how should the program behave in case "x - arr[mid] == arr[mid + k] - x". Currently my program always move towards left but thats failing for some test cases as mentioned above?

Upvotes: 0

Views: 105

Answers (1)

user3036345
user3036345

Reputation: 1

Posting the answer that I was able to figure out:

public List<Integer> findClosestElements(int[] arr, int k, int x) {

    int left = 0, right = arr.length - k;
    int start = 0;
    while (left <= right) {
        int midpoint = left + (right - left) / 2;
        if (((midpoint + k) < arr.length ) && (x - arr[midpoint] > arr[midpoint + k] - x))    {
            left = midpoint + 1;
            start = left;
        }
        else {
            start = midpoint;
            right = midpoint - 1;
        }
    }
    start = (start == arr.length)?start - 1: start;
    List<Integer> result = new ArrayList<>(k);
    for (int i = start; i < start + k; i++) {
        result.add(arr[i]);
    }
    return result;
}
}

Upvotes: 0

Related Questions