결정알고리즘 연습 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;




class Main {

	static int answer = 0;
	
	public static void main(String args[]) throws Exception {
		
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		
		int [ ]arr = new int[n];
		
		for ( int i = 0 ; i < n ; i++) {
			arr[i] = in.nextInt();			
		} 
		
		//마구간의 좌표를 정렬
		Arrays.sort(arr);
		// 최소간격을 1
		int lt = 1;
		// 최대 간격을 MAX , MIN 의 차이 값으로 설정한다.
		int rt = Arrays.stream(arr).max().getAsInt() - Arrays.stream(arr).min().getAsInt();
		int max = Integer.MIN_VALUE;
		
		
		while (lt <= rt) {
			int mid = (lt + rt)/2;
						
			//첫번째 말은 첫번째 구간에 배치한다.
			int cnt = 1;
			int horse = arr[0];
			for ( int i = 1 ; i < n ; i++) {
				//순회하면서 구간조건을 충족하는 곳에 말을 배치한다.
				if ( arr[i] - horse >= mid ) {
					horse = arr[i];
					cnt++;
				} 
			}			
			//말을 m마리 이상 배치할 수 있는 경우 중 구간(mid)의 최대값이 최적화된 값이 된다.
			if ( cnt >= m ) {
				max = Math.max(max, mid);
				lt = mid + 1;
			} else // 구간에서 정해진 말을 배치하지 못한 경우는 구간을 감소시킨다. 
				rt = mid - 1;			
		}
		
		
		System.out.println(max);
	}
		
		
	
}

ex)
input 
5 3
1 2 8 4 9

output
3