이진 검색과 시간 복잡도에 대해서

안녕하세요, 오늘은 검색 알고리즘의 두 번째 시간으로 이진 검색에 대해 알아볼 것입니다.
또한 저번에 배운 검색 알고리즘의 선형 검색과 이진 검색의 시간 복잡도에 대해서도 공부할 것입니다.

🤦‍♂️ 이진 검색은 또한 무엇인가?

검색 알고리즘에는 대표적으로 선형 검색과 이진 검색 두 가지가 존재합니다. 저번에 저희는 선형 검색에 대해서 알아보았습니다. 그럼 이번에 알아볼 이진 검색은 무엇일까요? 이진 검색은 배열의 각 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다. 이진 검색은 저번 선형 검색보다 좀 더 빠르게 값을 검색할 수 있다는 장점이 존재합니다. 아래의 그림을 보겠습니다.

 

요소의 값이 오름차순으로 구성되어있는 int 자료형의 배열입니다.

위의 배열은 오름차순으로 구성되어있는 int 자료형의 배열입니다. 저희는 이 위의 배열의 요 솟값 39를 찾아보려고 합니다. 선형 검색에서는 배열의 0번째 인덱스부터 순차적으로 검사를 하였다면 이진 검색은 인덱스의 중간, 중간씩 크게 크게 기준을 나누어 데이터 검색 비용의 횟수를 줄이는 방식으로 알고리즘이 동작됩니다. 그럼 본격적으로 위의 배열에서 숫자 39를 찾아보도록 하겠습니다.

 

오름차순으로 정렬된 int 정수형 배열에서 이진 검색 알고리즘을 활용하여 39를 검색하고 있습니다.

위의 과정은 실제로 이진 검색 알고리즘의 과정입니다. 첫 번째 A의 과정에서 검색을 시작할 때 Pl은 배열의 인덱스 첫 번째를 의미하며 Pr은 배열의 인덱스 마지막을 의미합니다. 마지막 Pc는 양 끝의 (Pl + Pc) / 2의 값이며 Pc는 값을 판단하는 용도로 이용됩니다.

 

처음 A의 검색 대상 범위는 배열 전체였지만 B, C로 갈 수록 검색 대상의 범위가 줄어드는 것을 볼 수 있습니다. 선형 검색과 같이 한 개씩 개별적으로 비교를 하는 것이 아닌 검색 범위를 반으로 좁혀지면서 빠르고 크게 값을 판단한다는 것을 알 수 있습니다.

 

※ 배열의 이름을 arr, 찾는 값 이름을 key라고 앞으로 부르겠습니다.

arr [Pc] < key 일 때

1. arr[Pl] ~ arr [Pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외가 됩니다. 

2. 검색 범위는 중앙 요소 arr[Pc]보다 뒤쪽의 arr [Pc + 1] ~ arr [Pr]로 좁혀집니다.

3. Pl의 값을 기존의 Pc + 1로 업데이트를 진행해야합니다.

arr [pc] > key 일 때

1. arr [Pc] ~ arr [Pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외가 됩니다.

2. 검색 범위는 중앙 요소 arr [Pc]보다 앞쪽 arr[Pl] ~ arr[Pc - 1]로 좁혀집니다.

3. Pr의 값을 기존의 Pc - 1로 업데이트를 진행해야 합니다.

🥇 이진 검색의 종료 조건은?

위에서 이진 검색의 개념과 구조를 알아보았습니다. 그럼 이진 검색의 종료 조건은 무엇일까요? 예상하셨나요? 저번 선형 검색과 크게 다르지 않습니다. 이진 검색 또한 같은 검색 알고리즘이기 때문에 같은 종료 조건을 가지고 있습니다. 한 번 더 복습하겠습니다!

 

이진 검색의 종료 조건

1. arr [Pc]와 key가 일치하는 경우 (검색 성공)

2. 검색 범위가 더 이상 없는 경우 Pl > Pr보다 큰 경우 (검색 실패)

첫 번째 종료 조건은 많이 익숙하실 것입니다. 하지만 두 번째 종료 조건은 이해가 되지 않으실 수도 있습니다. 위에서 사진으로 보았던 예시는 일반적인 배열에서 찾는 값이 존재하여 검색을 성공하는 예시였다면 이번에는 배열에 존재하지 않는 숫자 6을 찾아보도록 하겠습니다. 이 과정을 통해서 여러분은 이진 검색의 종료 조건 1, 2번을 모두 이해하실 수 있을 것입니다. 아래의 그림을 보겠습니다.

 

 

위의 사진은 일반적인 배열에서 숫자 6을 찾고 있습니다. 이진 검색 알고리즘을 활용하고 있으며 크기의 폭을 줄여가면서 값을 검색하고 있는 모습을 볼 수 있습니다. 그러나 마지막 E의 상황을 보면 Pr의 값이 Pl의 값 보다 더 큰 모습을 볼 수 있습니다. 이런 상황이 발생하면 배열 속에서 검색을 실패하였다는 의미이며 검색 범위가 더 이상 존재하지 않는다는 것입니다. 이제 이해가 되셨나요?

📢 이진 검색을 구현해보자!

그럼 이제 위에서 열심히 배운 내용을 코드로 직접 구현해보겠습니다. 또한 코드를 구현할 때 이진 검색의 검색 비용에 대해서 알아야 합니다. 이진 검색의 검색 비용은 평균 log n이며 검색에 실패한 경우는 log n +1회, 검색에 성공한 경우는 log n -1회 정도입니다.

public class BinSearch {
    public static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        System.out.print("요솟수를 입력해주세요 : "); int input = scanner.nextInt();
        int[] arr = new int[input];

        System.out.println("오름차순으로 입력해주세요");
        setArr(arr);

        System.out.print("배열에서 검색할 값을 입력해주세요 : "); int search_input = scanner.nextInt();
        int idx = searchArr(arr, search_input);

        if(idx == -1){
            System.out.println("찾으시려는 값은 배열에서 존재하지 않습니다. (검색 실패)");
        } else{
            System.out.println("찾으시려는 값은 배열의 arr[" + idx + "] 번재에 존재합니다. (검색 성공)");
        }
    }

    public static void setArr(int arr[]){
        for(int i = 0; i < arr.length; i++){
            System.out.print("arr[" + i + "] : "); int input = scanner.nextInt();
            if(i != 0 && input <= arr[i - 1]){
                while(true){
                    System.out.print("앞에 입력한 값보다 더 큰 숫자를 입력해주세요 : "); input = scanner.nextInt();
                    if(input > arr[i-1]) break;
                }
            }
            arr[i] = input;
        }
    }

    public static int searchArr(int arr[], int search_input){
        int pl = 0;
        int pr = arr.length - 1;
        int pc = (pl + pr) / 2;

        while(pr >= pl){
            if(arr[pc] == search_input){
                return pc;
            } else if(arr[pc] > search_input){
                pr = pc - 1;
                pc = (pl + pr) / 2;
            } else if(arr[pc] < search_input){
                pl = pc + 1;
                pc = (pl + pr) / 2;
            }
        }
        return -1;
    }
}

이진 검색을 활용하여 배열 속 값을 찾아내고 있는 모습입니다.

🎨 알고리즘의 복잡도에 대해서

앞에서도 말했듯이 어떤 문제를 해결해야 한다고 가정을 했을 때 해결 방법은 정말 다양합니다. 다양한 알고리즘과 방법들이 존재합니다. 그러면 어떤 방법을 활용해야 잘 활용을 하였다고 소문이 날까요? 그것을 판단해주는 기준이 복잡도입니다. 복잡도의 의미는 알고리즘의 성능을 객관적으로 평가하는 기준입니다. 복잡도의 종류로는 아래에 두 가지 요소가 존재합니다. 확인하시죠!

 

복잡도의 종류

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것

2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

⏰ 선형, 이진 검색의 시간 복잡도

이번에는 복잡도 종류 중에서 선형, 이진 검색의 시간 복잡도를 알아보도록 하겠습니다. 시간 복잡도는 O 기호를 사용하며 Order를 의미합니다. O 기호 뒤 소괄호에 시간 복잡도의 크기를 입력하면 됩니다. 만약 처음 한 번 실행한 이후 실행이 없는 것은 O(1) 복잡도라고 표기합니다. 그러나 만약 꾸준히 비교하고 검색을 수행한다면 평균 실행 횟수를 n / 2이며 복잡도로 O(n)이라고 표기합니다.

 

분명히 n / 2인데 왜 O(n/2)로 입력을 하지 않냐고 궁금해하실 수 있습니다. 이유는 컴퓨터 입장에서 n / 2의 크기와 n은 크기 차이가 존재하지 않는다고 판단합니다. 즉 컴퓨터가 100번을 검색하는 시간과 1번만 계산하는 시간의 차이는 사람이 느낄 수 없습니다.

 

시간 복잡도 공식

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

※ 최종적인 시간 복잡도는 같을 수 있으나 코드 구현에 따라 과정 속 일부 값들은 다를 수 있습니다.

선형 검색의 시간 복잡도

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)

이진 검색의 시간 복잡도

O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) +... + O(1) = O(log n)

시간 복잡도의 크기를 알려주는 표입니다.

👍 글을 마치며

이번에는 검색 알고리즘의 이진 검색 알고리즘과 시간 복잡도에 대해서 알아보았습니다. 저번 선형 검색 알고리즘보다는 조금 더 어려운 내용이었습니다. 처음에는 저도 이 내용을 어떻게 준비를 해야 하고 작성을 해야 하나 많이 고민을 하였습니다. 공부하였던 책들을 많이 참고해서 조금 더 쉽게 할 수 있었습니다. 저번 시간과 이번 시간을 통해서 배열을 활용한 검색 알고리즘은 모두 끝이 났습니다. 다음번에는 스택과 큐에 대해서 글을 작성할 것이며 조금 더 멋지 글을 작성할 수 있도록 저 또한 열심히 공부하도록 하겠습니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편