[개념 정리] 이분 탐색

이분 탐색이 뭘까요?

 

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

이분 탐색

정렬된 배열에서 탐색 범위를 절반씩 줄여가는 방식으로 특정 값을 찾는 알고리즘입니다.

이진 탐색이라고도 불리면, 시간 복잡도는 O(log N)이 걸립니다.

 

주로 크기가 큰 배열에서 어떠한 값을 찾아야하는 경우에 해당 배열을 정렬하고 이분 탐색을 사용하면, O(logN)의 시간복잡도로 효율적으로 값을 찾을 수 있습니다.

 

이분 탐색 동작원리

1. 가장 왼쪽 인덱스인 left와 가장 오른쪽 인덱스인 right를 설정합니다.

 

2. (left + right) / 2로 중간값인 mid를 계산합니다.

 

3. 값을 비교합니다.

• 목표값과 중간값이 같은 경우, 탐색을 종료하고 mid를 반환합니다.
• 목표값이 중간값보다 작은 경우, 오른쪽 절반을 탐색할 필요가 없으므로 right을 mid - 1로 설정하여, 왼쪽 절반만 탐색합니다.
• 목표값이 중간값보다 큰 경우, 왼쪽 절반은 탐색할 필요가 없으므로 left를 mid + 1로 설정하여, 오른쪽 절반만 탐색합니다.

4. left가 right보다 커질 때까지 반복합니다. 목표값을 찾지 못한 경우엔 -1을 반환합니다.

 

빨간색 화살표는 left, 파란색 화살표는 mid, 노란색 화살표는 right입니다. 찾아야 하는 값은 빨간색 점선입니다.

 

N = 14일때 3번만에 원하는 값을 찾았습니다.

log14는 3.xxxx이므로 시간복잡도가 O(logN)이 됩니다.

 

 

 

이분 탐색 적용

백준 가장 긴 증가하는 부분 수열 2

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

 

입력값
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력값
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

이 문제는 완전 탐색을 사용하면, 시간복잡도 O(N^2)이 걸리기 때문에 최악의 경우 1,000,000 x 1,000,000 이므로 무조건 시간초과가 발생합니다.

 

따라서, 이분 탐색을 사용해서 O(NlogN)의 시간복잡도로 구현해야 문제를 해결할 수 있습니다.

모든 수를 선형 탐색을 하되, 주어진 수가 들어갈 위치를 이분 탐색을 통해서 찾아주어야 합니다.

 

풀이 코드

public class Main {

    private static int A;
    private static int[] a;
    private static List<Integer> lis = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        A = Integer.parseInt(br.readLine());
        a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for(int i = 0; i < A; i++) {
            int value = a[i];
            if(lis.isEmpty() || lis.get(lis.size() - 1) < value) {
                lis.add(value);
            }else{
                int left = 0;
                int right = lis.size() - 1;

                while(left < right) {
                    int mid = (left + right) / 2;

                    if(lis.get(mid) < value) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }

                lis.set(left, value);
            }
        }

        System.out.println(lis.size());
    }

}

 

 

이분 탐색이 적용된 로직은 다음과 같습니다.

int left = 0;
int right = lis.size() - 1;

while(left < right) {
     int mid = (left + right) / 2;

     if(lis.get(mid) < value) {
         left = mid + 1;
     }else {
          right = mid;
     }
 }

lis.set(left, value);

 

값이 들어갈 위치를 최종적으로 left값으로 찾아 lis에 값을 넣어줍니다.

 

 

출력 결과