[알고리즘 기본 스킬] 이분 탐색 (Binary Search)

이분 탐색은 순차탐색으로 풀면 시간복잡도가 터져서 풀지 못하는 문제를 시간 복잡도를 LogN으로 줄여서 탐색의 시간을 줄여준다.

 

기본적으로 시작 인덱스와 끝 인덱스를 활용해서, 중간 인덱스 값을 구해서 값을 비교하면서 진행한다.

기본 조건으로 정렬이 되어 있어야한다.

당연한 말이지만 정렬이 되어있지 않으면, 탐색 과정에서 숫자의 대소 비교가 의미없다.

 

알고리즘에서 이분 탐색을 활용하는 것을 설명하겠다.

문제의 해답 코드로 설명한다.

 

Ref : https://blog.encrypted.gg/985

---

 

1. 가장 기본적인 이분 탐색

-> 시간복잡도 lgN이 필요할 경우 사용

 

문제 백준 1920번 

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

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st ;
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i< N;i++) {
        	int value = Integer.parseInt(st.nextToken());
        	arr[i] = value;
        }
        Arrays.sort(arr);
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        ArrayList<Integer> find = new ArrayList<>();
        for (int i = 0; i < M; i++) {
        	int value = Integer.parseInt(st.nextToken());
        	find.add(value);
        }
        for (int next : find) {
        	int lt = 0;
        	int rt = arr.length - 1;
        	boolean flag = false;
        	while (lt <= rt) {
        		int mid = (lt+rt)/ 2;
        		if (arr[mid] == next) {
        			sb.append(1).append("\n");
        			flag = true;
        			break;
        		}
        		if (arr[mid] < next) {
        			lt = mid+1;
        		}
        		else if (arr[mid] > next) {
        			rt = mid -1;
        		}
        		
        	}
        	if (!flag) sb.append(0).append("\n");
        }
        
        
        System.out.println(sb);
    }
}

 

 

2. 이분 탐색의 상한과 하한 

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

 

우선 기본적인 함수 구성을 설명하겠습니다. 

해당 문제는 주어진 숫자중 타겟 숫자가 몇개 들어있는지 출력하는 문제입니다.

여기서 간단하게 HashMap을 사용해서 푸는 방법도 있지만

 

이분 탐색의 상한과 하한의 차로 구하는 방법도 있습니다.

 

이분 탐색의 하한

target 숫자가 삽입될 수 있는 가장 왼쪽을 나타냅니다.

즉 해당 숫자가 없으면 새롭게 삽입되어야 할 위치이고, target보다 큰 가장 작은 수의 인덱스여야합니다.

존재하면 target 의 가장 작은 인덱스 위치를 반환합니다.

 

조건

- arr[mid] 값이 target 보다 크거나 같다 : 해당 위치일 수도 있다.

해당 위치 이하 라는 뜻이다. 존재하지 않는 숫자고 arr[mid]이 target보다 큰 가장 작은 수 일수도 있기때문이다.

 

- arr[mid] 값이 target 보다 작다 : 해당 위치보다 무조건 크다. 

작다는 것은 무조건 위의 위치라는 뜻이다.

 

이분 탐색의 상한 

target 숫자가 삽입될 수 있는 가장 오른쪽 위치.

즉 해당 숫자보다 큰 가장 작은 수의 인덱스여야하는 것 

 

조건

- arr[mid] 값이 target 보다 크다 : 해당 위치일 수도 있다.

해당 위치일 수도 있기에 범위를 좁혀서 탐색

 

- arr[mid] 값이 target 보다 작거나 같다 

해당 위치보다 무조건 위의 위치에 존재한다.

 

정답 코드 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i =0;i<N;i++) {
        	int value = Integer.parseInt(st.nextToken());
        	arr[i] = value;
        }
        Arrays.sort(arr);
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> save = new ArrayList<>();
        for (int i = 0;i<M;i++) {
        	int value = Integer.parseInt(st.nextToken());
        	save.add(value);
        }
        
        for (int find : save) {
        	sb.append(upperBound(arr, find) - lowerBound(arr, find)).append(" ");
        }
        System.out.println(sb.toString());
    }
    private static int lowerBound(int[] arr,int find) {
    	int lt = 0; int rt = arr.length;
    	while (lt < rt) {
    		int mid = (lt+rt) / 2;
    		if (arr[mid] >= find) rt = mid;
    		else lt = mid + 1;    		
    	}
 
    	return lt;
    }
    private static int upperBound(int[] arr,int find) {
    	int lt = 0; int rt = arr.length;
    	while (lt < rt) {
    		int mid = (lt+rt) / 2;
    		if (arr[mid] > find) rt = mid;
    		else lt = mid + 1;    
    	}
    	return lt;
    }
}

 

 

3. 세 수의 합 

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

 

arr[x] + arr[y] + arr[z] = arr[k] 

k값의 최대값을 구하는 문제인데 기본적인 풀이로 풀게 되면 N^4 걸리게 되므로 시간복잡도를 초과한다.

이 문제에서는 시간복잡도를 N^2 * Log N 으로 줄여야된다.

 

간단하게 순서로 생각하면 

3가지 합을 구하는 N^3 , 이분탐색 LogN

여기서 한단계를 더 나아가면 두 수의 합을 배열로 구해놓고 그 배열이 존재하는지 확인하는 LogN

총 합쳐서 N^2 * Log (N^2) -> O( N^2 * Log N ) 

 

import java.util.*;
import java.io.*;

public class Solution{
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		for (int i = 0; i < N ; i++) {
			int value = Integer.parseInt(br.readLine());
			arr[i] = value;
		}
		Arrays.sort(arr);
		ArrayList<Integer> two = new ArrayList<>();
		// two 배열 만들기
		for (int i = 0; i < N; i ++) {
			for (int j = i; j < N; j++) {
				two.add(arr[i]+arr[j]);
			}
		}
		int[] two_arr = two.stream().mapToInt(Integer::intValue).toArray();
		Arrays.sort(two_arr);
		// k를 찾기 
		for (int k = N-1; k >= 0; k--) {
			for (int l = 0;l < k ; l++) {
				if (binarySearch(two_arr,arr[k]-arr[l])) {
					System.out.println(arr[k]);
					return ;
				}
			}
		}
	}
	private static boolean binarySearch(int[] arr,int find) {
		int lt = 0; int rt = arr.length-1;
		while(lt <= rt) {
			int mid = (lt+rt) / 2;
			if (arr[mid] == find) return true;
			else if (arr[mid] > find) rt = mid -1;
			else lt = mid +1;
		}
		return false;
	}
}

 

4. Parametric Serach 

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

조금은 어려운 내용이지만 해당 분야의 쉬운 문제만 풀어볼 예정이다.

 

조건을 만족하는 최소/최대값을 구하는 문제를 결정 문제로 변환해서 이분 탐색을 수행하는 방법.

 

해당 문제에서는 N개를 만들 수 있는 랜선의 최대길이를 구하는 최적화 문제에서

랜선의 길이가 X 일때 N개 이상인지 이분 탐색하는 결정 문제로 풀 수 있는 것

 

또한 핵심은 parametric search에서는 증가함수거나 감소함수여야 된다는 것이다

 

import java.util.*;
import java.io.*;

public class Solution{
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int max = 0;
		int[] arr = new int[K];
		for (int i = 0; i < K; i++) {
			int value = Integer.parseInt(br.readLine());
			arr[i] = value;
			if (max < value) max = value;
		}
		int lt = 0 ; int rt = max;
		
		while (lt < rt) {
			int mid = (lt+rt+1) / 2;
			if (solve(mid,arr,N)) lt = mid;
			else rt = mid - 1;
		}
		System.out.println(lt);
	}
	private static boolean solve(int mid , int[] arr,int n) {
		long sum = 0;
		for (int i = 0 ; i < arr.length; i++) {
			sum += arr[i] / mid; 
		}
		return sum >= n;
	}
}