[Java] 이분 탐색(Binary Search)

공부를 목적으로 진행하는 포스팅으로 만약 틀린 부분이 있거나 미흡한 점이 있으면 피드백 부탁드리겠습니다.

 

 이분 탐색 혹은 이진 탐색이라 불리는 이 알고리즘은 간단하면서 굉장히 효율적인 알고리즘입니다. 이 알고리즘을 수행하기 위해서는 기본적으로 정렬이 되어있어야 합니다. 정렬된 자료구조 안에서 특정 값을 찾을 때 절반씩 나누어 값을 찾는다는 것이 핵심적인 아이디어입니다. 

 

 이분 탐색은 탐색을 진행할 때마다 탐색 범위를 반으로 줄입니다. 분할 정복(Divide Conquer)알고리즘과 유사한데 이분 탐색은 분할 정복 알고리즘의 한 예입니다.

 

 만약 탐색 범위가 더이상 나눠지지 않는 1이 될 때의 탐색 횟수를 T라고 하고, 정렬된 배열의 길이가 N인 자료구조에서 이분 탐색을 했을 경우의 시간 복잡도를 표로 보여드리겠습니다.

탐색 횟수	범위
0	N
1	N/2 => N/2^1
2	N/4  => N/2^2
3	N/8  => N/2^3
T	N/?  => N/2^T

빅오 표기법 기준으로 최악의 경우를 T라 가정한다면 N/2^T = 1 이므로, T = log2​(N)임을 보입니다. 

 

 컴퓨터는 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용합니다. 즉, lon2N 표기법이 logN으로 쓰입니다. 그러나 로그의 밑이 변할 때, loga(N)과 logb(N)은 오로지 상수 승수에 따라서만 달라지며 이것은 빅오 표기법에서 버림 합니다. 그러므로 O(log N)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 됩니다. 

 

출처 : 

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84#%EB%A1%9C%EA%B7%B8_%EC%8B%9C%EA%B0%84_(Logarithmic_time)

 

즉, 이분 탐색 알고리즘은 log2(N) => logN 시간 복잡도를 가진다고 할 수 있습니다.

 

이분 탐색 유형의 문제를 풀이할 때는 대게 3가지 변수를 사용합니다. (변수명은 취향 차이입니다.)

Start = 0

End = 배열의 길이 -1

Mid = (Strat + End) / 2

 

또한, 대표적으로 3가지 아이디어를 기억하시면 됩니다. (오름차순 기준) 

 

1) 찾고자 하는 값이 배열[Mid]의 값보다 큰 경우, Start 값을 증가시킵니다. 

Start = Mid + 1

2) 찾고자 하는 값이 배열[Mid]의 값보다 작은 경우, End 값을 감소시킵니다.

End = Mid - 1

3) 찾고자 하는 값이 배열[Mid]에 위치한 경우, Mid를 반환합니다.

return Mid

 

간단하게 예를 들어 설명해보겠습니다. 

index	0	1	2	3	4
배열 값	1	3	5	7	9

 이런 배열이 주어졌다고 가정하고, 찾는 값은 7이라고 하겠습니다. 하지만 배열 안에 어떤 값들이 들어 있는지 모릅니다. 그렇다면 7을 찾기 위해 배열의 처음부터 끝까지 반복문을 통해서 탐색해야 합니다. 만약 배열의 길이가 1억 이상이고 찾고자 하는 7이 배열의 마지막 인덱스에 위치해 있으면 7을 찾기 위하여 배열의 마지막까지 쓸데 없는 탐색을 해야 할 것입니다.    

index	0	1	2	3	4
배열 값	1	3	5	7	9

 Start와 End는 파란색 Mid는 빨간색으로 표현하겠습니다. (0+4) / 2 = 2 = Mid입니다. 

Mid가 위치한 값은 5이고 찾고자 하는 값은 7이므로 Start의 값을 증가시키겠습니다. (Start = Mid + 1)

 

index	0	1	2	3	4
배열 값	1	3	5	7	9

Start = 3, End = 4 , Mid = (3 + 4) / 2 = 3 (나머지 버림)

 

 Mid가 위치한 값은 7로, 찾고자 하는 7을 찾을 수 있었습니다. 이분 탐색 알고리즘을 사용하지 않았다면 0~3까지 탐색해야 했지만, 사용함으로써 단 2회 만에 원하는 값을 찾을 수 있었습니다. 주어진 예제가 길이가 작아 차이가 없어 보일 수 있지만 길이가 크다면 효과는 강력합니다.

 

 문제 유형마다(최대, 최소를 구하는 문제 등) 코딩 방법이 달라지겠지만 큰 틀은 벗어나지 않습니다. 문제를 풀 때 주의할 점은 Mid를 잡는 기준을 잘 생각해야 합니다. 보통 배열의 Index를 잡긴 하지만 난이도가 있는 문제를 풀 때는 꼭 Index만이 Mid의 기준이 아닙니다. 

 

몇 가지 문제를 보여드리겠습니다.

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

대표적인 이분 탐색 문제입니다. 난이도도 그리 높지 않고 쉽게 연습할 수 있는 문제입니다.

public class BOJ_1920 {
	// BOJ / 1920번 / 수 찾기 / 이분탐색 / 실버4
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int arr[] = new int[n];
		
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(stk.nextToken());
		}
        	// 정렬
		Arrays.sort(arr);
		
		int t = Integer.parseInt(br.readLine());
		stk = new StringTokenizer(br.readLine(), " ");
		StringBuffer sb = new StringBuffer();
        
		while(t-->0) {
			int target = Integer.parseInt(stk.nextToken());
			if(binarySearch(arr, target)) {
				sb.append(1);
			}
			else {
				sb.append(0);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static boolean binarySearch(int []arr, int target) {
		int start = 0;
		int end = arr.length-1;
		int mid;
		while(start <= end) {
			mid =  (start + end) / 2;
			
			if(arr[mid] == target) return true;
			else if(arr[mid] < target) {
				start = mid + 1;
			}
			else if(arr[mid] > target) {
				end = mid - 1;
			}
		}
		return false;
	}
}

 

 사실 Java에는 이분 탐색을 사용할 수 있는 라이브러리가 존재합니다. 바로 Arrays.binarySearch()입니다.

하지만 이 라이브러리는 우리가 자주 봐왔던 구현 방식이 조금 달라서 주의가 필요합니다.

 

 간단하게 설명하자면, 파라미터는 (배열, 찾고자 하는 값) 이렇게 받습니다.

반환 값은 찾고자 하는 값이 존재하면 그 값의 인덱스를 반환하고, 존재 하지 않으면 그 값을 끼워 넣어 1부터 시작하는 인덱스를 음수로 변경하여 반환합니다.

 

아래 코드는 똑같은 문제를 Arrays.binarySearch() 메소드를 사용하여 풀이했습니다. 

public class Main {
	// BOJ / 1920번 / 수 찾기 / 이분 탐색 / 실버4
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		int n = Integer.parseInt(br.readLine());
		long a[] = new long[n];
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		
		for(int i=0; i<n; i++) {
			long input= Long.parseLong(stk.nextToken());
			a[i] = input;
		}
		Arrays.sort(a);
		
		int m = Integer.parseInt(br.readLine());
		long b[] = new long[m];
		stk = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<m; i++) {
			long input = Long.parseLong(stk.nextToken());
			b[i] = input;
		}
		
		for(int i=0; i<m; i++) {
			long num = b[i];
			
			boolean find = false;
			if(Arrays.binarySearch(a, num) >= 0) {
				find = true;
				sb.append(1).append("\n");
			}
			
			if(!find) sb.append(0).append("\n");
		}
		
		System.out.println(sb);
	}
}

이 메소드를 적절히 활용한다면 괜찮겠지만 직접 구현을 해봐서 나만의 것으로 만드는게 더 중요합니다. 

 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

위 문제는 Mid 기준을 Index가 아닌 다른 기준으로 설정했을 때 유형입니다. 

public class PM_43238 {
	// PM / 43238번 / 입국심사 / 이분 탐색 / Level3 
	
    public static long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        
        long start = 0;
        long end = Long.MAX_VALUE;
        long mid;
        Arrays.sort(times);
        
        while(start <= end) {
        	// m은 주어진 시간 
        	mid = (start+end) / 2;
        	
        	long sum = 0;
        	// 주어진 시간 동안 각 심사대에서 총 몇명이 심사 받을 수 있는지 센다. 
        	for(int i=0; i<times.length; i++) {
        		sum += (mid / times[i]);
        		if(sum >= n) {
        			break;
        		}
        	}
        	// 모든 사람이 주어진 시간 내에 심사를 할 수 없으면 
        	if(sum < n ) {
        		start = mid+1;
        	}
        	// 모든 사람이 주어진 시간 내에 심사를 할 수 있으면 
        	else {
        		end = mid-1;
        		answer = Math.min(answer, mid);
        	}
        }
        System.out.println(answer);
        return answer;
    }
}

인덱스가 아닌 주어진 시간을 Mid로 잡아 문제를 풀이하였습니다. 

 

https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리

public class PM_43236 {
	// PM / 43263번 / 징검다리 / 이분탐색 / Level4 

    public static int solution(int distance, int[] rocks, int n) {
        int answer = Integer.MIN_VALUE;
        
        Arrays.sort(rocks);
        
        int start = 0; 
        int end = Integer.MAX_VALUE;
        int mid;
        
        while(start <= end) {
        	// mid는 바위 사이의 거리 
        	mid = (start + end) / 2;
        	int count = 0;
        	int prev = 0;
        	for(int i=0; i<rocks.length; i++) {
        		// mid보다 작으면 삭제 
        		if(rocks[i] - prev < mid) {
        			count++;
        		}
        		// mid보다 크거나 같으면 prev 변경
        		else {
        			prev = rocks[i];
        		}
        		if(count > n) break;
        	}
        	// 마지막 비교 
        	if(distance - prev < mid && count<=n) {
        		count++;
        	}
        	// 삭제된 바위가 n개보다 크면  
        	if(count > n) {
        		end = mid - 1;
        	}
        	// 삭제된 바위가 n개보다 작거나 같으면  
        	// 최댓값을 구해야 하므로 start에서 mid 변화
        	else {
        		start = mid + 1;
        		answer = Math.max(answer, mid);
        	}
        	
        }
        System.out.println(answer);
        return answer;
    }
}

 

 위 문제 또한 Mid의 기준을 본인이 설정해야 합니다. 사실 이분 탐색 문제는 출제자가 이미 Mid의 기준을 생각하고 출제하는 듯합니다. 그 의도를 파악하는 것이 쉽지 않을뿐..

 

 이분 탐색 알고리즘은 효율성 문제에서 많이 출제되지만 간단한 코드와는 다르게 난이도가 있는 문제들이 많습니다. 유형을 반복해서 풀어보고 경험을 쌓는 것이 중요해 보입니다.