[알고리즘] 이진탐색(binary search)

이번 시간에는 이진탐색에 대해서 알아보겠습니다.

 

44 6 9 10 21 45 67 100이라는 숫자에서 45라는 숫자가 있는지 없는지, 혹은 몇번째에 있는지 어떻게 찾을 수 있을까요 ?

가장 간단한 방법은 앞에서 부터 하나씩 세어 나가는 것입니다. 44,6,9,10.....이런식으로 가다보면 45가 6번째에 있다는 것을 알 수 있습니다.

 

만약, 데이터가 10억개 이고 그 중에 한 원소를 찾는다고 했을 때, 정~말 운이 좋다면 첫번째에 찾는 값이 있어서 바로 찾을 수 있습니다. 근데 운이 안좋다면 10억번째에 원하는 값이 있을 수 있겠네요. 이와 같은 방법으로 앞에서부터 하나씩 찾아간다면 시간복잡도는 O(N)이 됩니다. 

 

N이 만약 엄청 큰 숫자라면 당연히 연산하는데 굉장히 오랜 시간이 걸리게 될 것입니다. 이 연산횟수를 줄일 수 있는 좀 더 나은 방법이 없을까요 ?

 

이진탐색은 검사하는 구간을 반 씩 줄여서 나가는 방법입니다. 예를 들어서 44 6 9 10 21 45 67 100에서 찾으려는 값(45)이 가운데에 위치해 있는 값(21)보다 큰지 작은지 검사합니다.

 

45 > 21이기 때문에 21왼쪽에 있는 값들은 신경쓰지 않아도 됩니다. 왜냐하면 21왼쪽에 있는 값들을 당연히 21보다 작은 값이기 때문이죠.

여기서 12왼쪽에 있는 값들이 당연히 21보다 작다는것이 당연한 이유는 데이터들이 기본적으로 "정렬" 되어있기 떄문입니다.

 

근데 만약, 데이터들을 한번 정렬하고 다시 이진탐색을 한다면 비효율적인거 아닌가? 라는 생각이 들 수 있습니다.

맞습니다. 하지만 이미 데이터가 정렬되어 있다고 가정한다면 이진탐색이 엄청 효율적입니다.

그리고, 만약 숫자를 찾아야 하는 경우가 엄청 많은 경우라면 정렬하고 이진탐색을 하는 것이 좋습니다.

ex) 데이터가 100개이고, 숫자찾기를 10000번 해야 하는 경우

 

1. 재귀적으로 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int num;
        boolean result = false;

        for (int i = 0; i < m; i++) {
            num = sc.nextInt();

            result = binarySearch(arr, 0, arr.length - 1, num);

            if (result) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    static boolean binarySearch(int[] arr, int start, int end, int num) {
        if (start > end) {
            return false;
        } else if (start == end) {
            if (arr[start] == num) {
                return true;
            } else {
                return false;
            }
        }

        int mid = (start + end) / 2;
        if (arr[mid] == num) {
            return true;
        }

        if (arr[mid] > num) {
            return binarySearch(arr, start, mid - 1, num);
        } else {
            return binarySearch(arr, mid + 1, end, num);
        }
    }
}

간단하게, binarySearch는 arr배열에서 start부터 end까지 구간에서 num을 찾는 과정을 수행하는 재귀함수 입니다.

 

기저 조건으로는

false : start가 end는 보다 클 때(숫자가 존재하지 않는 경우), start와 end가 같고(숫자가 하나 있고), start 번째의 값이 num이 아닌경우

true : start와 end가 같고, start번째 값이 num인 경우, 그리고 start와 end에서 가운데 값 mid번째 값이 num인 경우

 

이 경우가 아니라면, mid번째 값보다 num이 큰지 작은지에 따라 start와 end값을 수정해서 다시 재귀함수를 돕니다.

 

 

2. 비 재귀적 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int m = sc.nextInt();

        int start, end, mid;
        // start : m보다 무조건 작은값
        // end : m보다 무조건 큰 값

        start = 0;
        end = n - 1;

        if (arr[start] > m && arr[end] < m) {
            System.out.println(-1);
            return;
        } else if (arr[start] == m) {
            System.out.println(start + " 번째에 있습니다.");
            return;
        } else if (arr[end] == m) {
            System.out.println(end + " 번째에 있습니다.");
            return;
        }

        while (start + 1 < end) {
            mid = (start + end) / 2;

            if (arr[mid] == m) {
                System.out.println(mid + " 번쨰에 있습니다.");
                return;
            }

            if (arr[mid] > m) {
                end = mid;
            } else if (arr[mid] < m) {
                start = mid;
            }
        }
        System.out.println("찾으려는 숫자가 없습니다.");
    }
}

비 재귀적 구현은 단순히 반복을 사용하여 숫자를  찾습니다. 예를 들어서 5 7 10 15 21 29 30 에서 7을 찾는 방법은 다음과 같습니다(편의상 코드의 start는 s, end는 e로 하겠습니다).

 

5 7 10 15 21 29 30

s          m           e  

여기서 s,e는 값이 아니라 5,30의 인덱스값입니다. 현재 mid는 (0+6)/2 = 3입니다. mid위치에서 값은 15입니다.

15 > 7이기 때문에 e에 mid값을 넣어 줍니다. 왜냐하면, e는 항상 m보다 큰 값이기 때문입니다.

 

5 7 10 15 21 29 30 

s      m e               

위와 다시 m값을 구하고, 10은 7보다 크기 때문에 e의 자리를 옮겨줍니다.

 

5 7 10 15 21 29 30 

s  m e                   

여기서 m에서의 값은 7이므로, 원하는 값을 찾았습니다.

근데 만약, 여기서 찾고 싶은 값이 7이 아니라 6이면 어떻게 될까요 ?

 

5 7 10 15 21 29 30 

s e                        

6을 찾는 경우면  s와 e는 붙어있는 상황이 되고 이는 즉, 끝까지 찾아봤는데 6이 없다라는 의미가 됩니다.

while문 조건이 false가 되고 숫자를 찾을 수 없다라고 출력을 합니다.