이진탐색

이진탐색

데이터가 정렬되어 있는 경우 원하는 값을 찾아내는 알고리즘
시간복잡도는 logN이다.

구현과정

1. 데이터 정렬
2. 데이터의 중앙값을 선택
3. 중앙값과 원하는 값을 비교하여 중앙값을 기준으로 다시 탐색을 시작한다.
4. 중앙값과 원하는 값이 같은경우 탐색을 종료한다.

구현코드 - 백준 2343블루레이 만들기

public class Q30 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		
		int lesson = Integer.parseInt(st.nextToken());
		int bluelay = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[lesson];
		int max = 0;
		int sum = 0;
		
		st = new StringTokenizer(in.readLine());
		for(int i=0; i<lesson; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			sum = sum + arr[i];
			if(max<arr[i]) max = arr[i];
		}
		
		int start = max;
		int end = sum;
		
		while(start<=end) {
        //start<end가 아닌 start<=end를 해야하는 이유 생각해보기!!!!!
		// ----> start==end인 경우에 m의 값을 계산하지 않기 때문에 start<end이면 모든 범위를 탐색하지 못한다. 
		//start<=end 인 경우에만 모든 범위를 탐색할 수 있다.
			int m = (start + end)/2;
			int psum = 0;
			int count = 0;
			for(int i=0; i<lesson; i++) {
				if(psum + arr[i]>m) {
					count++;
					psum = 0;
				}
				psum = psum + arr[i];
			}
			if(psum != 0) count++;
			
			if(count > bluelay) {
				start = m+1;
			}else {
				end = m-1;
			}		
		}
		System.out.println(start);
	
		

	}

}