Maximizing Minimum Distance Between Magnets in Boxes

We have n boxes in which we have to place c magnets such that minimum distance between two magnet should be maximum.

As we know any two magnet become aggressive when kept close to each other so we keep them as apart as possible.
While keeping apart we calculate the minimum distance which we maximized.

Input format:

Line 1: Two space-separated integers: n and c 
Line 2: n integers indicating location of boxes. 

Examples:

Input : 10 4
0 3 4 7 11 13 17 15 19 24
Output : 7
0,7,17,24 are allotted.

Input : 10 3
0 9 11 32 44 56 78 92 98 100
Output : 44
0,44,100 or 0,56,100 are alloted

Approach:
Fist solution comes to our mind is to one by one allot the boxes using greedy approach but that will not work because at any instance the prior decision is not the best decision.
So we create binary search on possible distances, we allot the magnets according to that distance and after allotment we make certain decision on the condition of the remaining boxes or the remaining magnets.

If we know the solution suppose it is ans then we can say that if taking ans as at-least distance between any two magnet then there will be no magnet remain and it will be perfectly allotted. But if we take at-least distance be ans+1 then there will at-least one magnet remaining to allot.

We would run a binary search for at-least distance and at every it will traverse the whole array for allotment. Here what it would looks like, we would try to allot magnets with certain at-least distance.

At last if all magnets are done and there are might more boxes remaining then we say lower boundary should be change to current at-least distance and if boxes are done and some magnets are still remaining then we would say change the upper boundary to the current at-least distance.
The complexity of this solution would be O(n*(log n)). log n for binary search and n for each time traversing the whole array.

Read the code it will make more sense.

import java.util.Arrays;
import java.util.Scanner;

public class discretebinarysearch {
    public static void main(String ar[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        int ld = 0; // least distance
        int hd = arr[n - 1] - arr[0] + 1; // maximum distance
        int md = hd; // middle distance
        while (hd - ld > 1) {
            int x = 1; // counter of the number of magnets allotted
            int prp = arr[0]; // previous allotted magnet
            int max = Integer.MAX_VALUE;
            for (int i = 1; i < n; i++) { // allotting the magnet keeping the minimum distance=md
                if ((arr[i] - prp) >= md) {
                    max = Math.min(max, arr[i] - prp);
                    ++x;
                    prp = arr[i]; // changing the value of the previous allotted magnet
                    if (x == c)
                        break;
                } else
                    continue;
            }
            if (x == c)
                ld = md;
            else
                hd = md;
            md = ld + (hd - ld) / 2;
        }
        System.out.println(ld);
    }
}

Time complexity: O(n log n)
Space complexity: (n)