[알고리즘] 이진 탐색

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이며 대상 데이터 탐색

기능

타깃 데이터 탐색

특징

중앙값 비교를 통한 대상 축소 방식

시간 복잡도

O(logN)

ex) 맨 처음 원소의 개수가 8에서 4, 2, 1 으로 반씩 점차 줄어드는 것을 확인할 수 있다. 즉, 위의 경우 N=8일 때 탐색이 3회 수행 됐으므로 시간 복잡도는 3이 된다.

일반화하여 생각해보자. N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, … , 1 으로 실행 될 것이다. 여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면, K는 N에 대해 어떻게 나타낼 수 있을까?
1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N

핵심이론

오름차순으로 정렬된 데이터에서 다음의 4가지 과정 반복
(내림차순이면, 조건을 반대로하여 과정 반복)

1. 현재 데이터셋의 중앙값 선택
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋 선택
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋 선택
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

이렇게 이진탐색을 사용하면 총 N개의 데이터에서 최대 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

단! 데이터가 정렬되어 있어야 한다.

---

N의 제곱근 구하기

이진 탐색은 위에서 말했듯이 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다.

양의 정수 N 이 주어졌을 때 N의 제곱근 √N 을 구하는 소스코드를 작성해보자. 단, 제곱근 값이 정수 일 경우에만 출력한다.

예를들어,

N = 100 -> 10
N = 25 -> 5
N = 10 -> -1
N = 1 -> 1

와 같이 출력한다.

단순히 생각해서 0부터 n-1 까지 자연수를 하나씩 증가시켜 가면서 확인해보면 구할 수 있을 것이다.

public static int squareRootLoop(int n) {
    for (int i=0; i<n; i++)
        if (i * i == n)
            return i;
    return -1;
}

이는 최악의 경우 n까지 모두 살펴봐야하므로, O(N)이 된다.

제곱근의 값은 N/2 보다 작거나 같다는 특징을 이용하여 반복문의 조건을
for (int i=0; i<=n/2; i++) 로 바꾸면 성능이 개선되겠지만, 상수 계수는 시간 복잡도에서 무시되므로 시간복잡도는 여전히 O(N)이다.

이진 탐색을 이용해보자

문제 접근을 조금 다르게 해보자.
우리는 지금 0부터 N까지의 자연수 중에 N의 제곱근이 있는지 없는지를 찾아보고 있다.
즉, 0부터 N까지의 정렬된 자연수에서 특정 값을 찾고 있는 것이다.
이진 탐색을 이용하여 코드를 다시 작성한다면 시간 복잡도를 O(logN)까지 줄일 수 있을 것이다.

public static int squareRootBSearch(int n) {
    int min = 0;
    int max = n;
    int guess;

    while (min <= max) {
        guess = (min + max) / 2;
        if (guess * guess == n)
            return guess;
        else if (guess * guess > n)
            max = guess - 1;
        else
            min = guess + 1;
    }
    return -1;
}

참고
https://cjh5414.github.io/binary-search/
Doit!알고리즘 코딩 테스트(자바편)