[자료구조 및 프로그래밍] 13. Binary Search & Sequential Search

Binary Search

이분 탐색은 어떤 정렬된 데이터에 대해 특정 값을 찾을 때, 반씩 나누어 탐색하여 log 시간에 데이터를 찾는 알고리즘이다.

사이즈 n 의 다음과 같은 배열이 있다고 해보자.

 

K1 < K2 < .... < Kn

 

그리고 이때, 다음과 같은 알고리즘을 이용하면 K 를 찾을 수 있다.

 

1. l = 1, u = n 으로 초기화

2. m = (l + u) // 2 (2로 나눈 몫, floor)

3. K 와 Km 을 비교한다.

만약 Km == K 이면, 값을 찾았으니 그대로 멈춘다.

만약 Km < K 이면, 찾는 값은 Km 기준 오른쪽에 있다.

따라서 l = Km + 1 으로 설정한다.

만약 Km > K 이면, 찾는 값은 Km 기준 왼쪽에 있다.

따라서 u = Km - 1 으로 설정한다.

4. 만약 u < l 이 되면, 값을 찾는데 실패한 것이고, 아니라면 다시 2번 단계로 돌아간다.

 

arr[n] <- sorted array
l, r <- 1, n
while (l < r) {
    m = (l+r) / 2
    if (K == arr[m])
        return l // found!
    if (K < arr[m])
        r = m - 1
    else
        l = m + 1
}

// not found!
return -1

 

 위 알고리즘을 보면, 시작과 끝을 나타내는 인덱스 l, u 는 고정되어 있지 않고 계속 변한다.

그리고 초기 l, u 의 값은 반드시 1, n 일 필요는 없다.

0, n-1 이 되어도 되고, l < u 를 만족하는 어떤 값이어도 된다.

 

또 m 값을 지금은 floor 로 구했지만, ceil 로 올림하여도 탐색을 진행할 수 있다.

 

이분 탐색과 비슷하게 정렬된 배열에서 값을 찾는 알고리즘 중 '피보나치 탐색' 이라는 것이 있다.

https://blog.naver.com/PostView.naver?blogId=minj2477&logNo=221863884676&parentCategoryNo=&categoryNo=31&viewDate=&isShowPopularPosts=true&from=search

[자료구조] 피보나치 검색

관련 내용은 이 블로그 글에 있는 GIF 를 보고 이해했다.

이분 탐색의 실행 시간

이분탐색은 탐색 범위가 반씩 줄어들다가 범위가 1이 되는 순간 값을 찾았는지 못찾았는지 판별된다.

처음에는 N개, 다음엔 N/2개, 다음엔 N/4 개 .... 결국 N/2^k 개가 1이 되는 순간 (정확히는 1이하가 되는 순간) 종료된다.

따라서 N/2^k <= 1 이 되는 k번 동안 반복문을 돈다.

 

N/2^k <= 1

N <= 2^k

log(N) <= k

 

따라서 O(log(n)) 시간이 걸린다.

이분 탐색에서 비교 횟수

이분 탐색의 실행시간은 키값 비교 횟수와 관련이 있다.

이분 탐색의 진행 과정을 이진 트리로 표현해보면, 키값 비교 횟수를 알 수 있다.

 

처음에는 0~9 범위에서 찾으니 m = 4 가 된다.

만약 4보다 작은 곳에 있다면 다음 탐색 범위는 0~3 이되고, m = 1

만약 4보다 큰 곳에 있다면, 다음 탐색 범위는 5~9 가 되고, m = 7

 

이런 식으로 트리를 그리면  아래와 같이 된다.

 

4는 1번의 비교만으로 찾을 수 있고,

6은 4번의 비교끝에 찾을 수 있다.

 

그런데 이 트리를 "값을 찾는다" 라는 상황에서만 유효한 트리이다.

값을 찾지 못할 때는 한번 더 깊게 탐색을 해야 한다.

즉, BST 에서 Extend Binary Tree 개념을 이용하면 된다.

 

그러면 위 그림과 같이 된다.

아래에 적은 숫자는 그 숫자를 탐색하려고 한다면.. 의 느낌으로 적었다.

최악의 경우 4번의 비교를 해야 값이 없다는 것을 알 수 있다.

 

처음에는 6 다음으로 5.5, 6.5 는 5번 타고가야 되는거 아닌가? 라고 헷갈렸었는데,

만약 찾으려는 키값과의 비교를 기준으로 비교 횟수를 센다면, 6.5도 4번 탐색으로 갈 수 있다.

키값 비교는 m 값이 정해지고 나면, ary[m] 과 키를 비교하는 방식으로 진행되는데, 만약 6~6 범위에서 값을 찾지 못했다면, l, u 값이 새로 설정되면서 서로 값이 역전되고 (l > u) 그 이후에는 반복문을 빠져나가므로, m 값도 갱신하지 않고 찾으려는 키 값과의 비교도 일어나지 않는다.

 

그리고 이분탐색은 그 특성상 정확히 반을 나누어 탐색을 진행하므로,

이분 탐색의 트리는 거의 완전한 이진 트리가 그려진다. (트리의 높이가 항상 최소를 유지한다.)

 

여기에 대해 한번 이분 탐색의  트리 표현에 대해 평균 키값 비교 횟수를 구해보자.

 

키값을 1번 비교 = 1개

키값을 2번 비교 = 2개

키값을 3번 비교 = 4개

키값을 4번 비교 = 3개

 

따라서 1 * 1 + 2 * 2 + 3 * 4 + 4 * 3 = 1 + 4 + 12 + 12 = 33

33 / 9 = 3.6xxxx

 

따라서 평균 키값 비교 횟수는 약 3~4번이다.

이는 트리의 평균 depth 를 구하는 것과 같다.

즉, 평균적으로 이분 탐색의 트리 표현에서 트리의 평균 깊이만큼 비교한다.

---

이분 탐색과 선형 탐색

위에서 살펴봤듯 이분 탐색은 log 시간에 원하는 키를 아주 빠르게  찾을 수 있는 알고리즘이다.

그런데 과연 항상 이분탐색이 O(n) 시간이 걸리는 선형 탐색보다 빠를까?

 

선형탐색은 데이터 리스트의 요소를 주어진 순서애돌 하나하나 확인하면서 데이터를 탐색하는 방법이다.

보통 선형탐색은 아래와 같이 구현한다.

seq_search(key) {
    for (i <- 0; i < N; i++) {
        if (key == data[i])
            return i
    }
    return -1
}

 

m 을 반복문이 종료될 때까지 반복한 횟수라고 해보자.

만약 데이터를 찾는데 성공했다면 m < N 일 것이다. (반복문은 0부터 N-1까지 도는데 왜 N '미만' 일까..?)

반면 데이터를 찾는데 실패했다면 m = N 일 것이다. (N+1 아닌가..?)

 

만약 data 배열 안의 데이터가 모두 동일한 확률로 탐색된다면, m 의 기댓값은 (1 + N) / 2 일 것이다.

따라서 이 알고리즘의 실행 시간은 대략 C * m 이 된다. (C 는 상수)

평균적인 경우와 최악의 경우 모두, 시간복잡도는 O(N) 이 된다.

 

보통 선형 시간 알고리즘은, 이분 탐색보다 훨씬 느리다.

그러나 어떤 경우에는 선형 시간 알고리즘이 이분탐색보다 더 적합한 경우가 있다.

 

첫 번째 상황은, 배열이 아니라 연결 리스트를 사용하는 경우다.

연결리스트는 random access 를 할 수 없으나 이분탐색은 random access 를 하기 때문이다.

 

두 번째 상황은, 데이터가 자주 추가되지만, 탐색은 비교적 자주 일어나지 않을 때이다.

이분 탐색은 데이터가 '정렬' 되어있어야 한다.

그러나 데이터가 자주 추가되는 상황에서 자주 일어나지도 않는 이분 탐색을 위해 그 데이터를 고려하여 정렬상태를 유지하는 것은 별로 효율적이지 않다.

 

그런데, 아까 위에서 작성한 선형탐색보다 조금 더 효율적인 선형탐색 테크닉이 있다.

아래 코드를 보자.

seq_search_sentinel(key) {
    data[N] <- key // sentinel
    while (key != data[i]) i++
    if (i < N) return i
    return -1
}

 

일단 기존 data의 마지막에 key를 넣어주고, 무작정 선형탐색을 돌린다.

key는 반드시 존재하기 때문에 i 를 반드시 구할 수 있다.

이제 구한 i 값을 마지막에 한번만 비교해주면 된다.

 

위 코드는 비록 반복문 내부에서는 탐색 범위에 대한 체크가 없지만, 아무리 오래 걸려도 반드시 N+1 번째 반복에서 프로그램이 종료됨이 보장된다.

 

이 알고리즘도 전에 작성했던 선형 탐색과 마찬가지로 탐색에 성공하는 경우, (N+1) / 2 의 반복문을 돈다.

단 탐색에 실패하면 N +1 번의 반복문을 돈다.

 

한번 두 알고리즘의 실행 시간을 비교해보자.

이를 위해 다음과 같은 값을 정의한다.

 

C1 : 키값 비교 횟수 (key == data[i] or key != data[i])

C2 : 범위 체크 (i < N) 횟수

I : 인덱스 증가 횟수

 

첫번째 알고리즘은 매번 범위를 체크하면서 반복문 내에서 키값도 비교하고 있다.

또 현재 범위의 체크가 끝나면 인덱스도 증가시킨다.

이 과정이 매 반복마다 일어나므로, 총 실행시간은 다음과 같다.

 

(C1 + C2 + I) * m + return 시간

 

그리고 새로 작성한 알고리즘은 범위체크 없이 키값만 비교하다가, 반복문이 끝나고 마지막에 키값의 범위를 한번 체크한다.

인덱스는 매 반복마다 증가한다.

따라서 총 실행시간은 다음과 같다.

 

(C1 + I) * m + C2 + return 시간 + data[N] <- K 할당 시간

 

이는 조금 거칠게 말해서 두번째 알고리즘이 첫번째 알고리즘보다 1 - (C1 + I )  / ( C1 + C2 + I ) 만큼 시간이 덜 걸린다고도 볼 수 있다.

 

반면 이분탐색은 어떨까?

C1 : 키값 비교횟수 ( key == data[mid] )

C2 : 인덱스 체크 횟수 (l <= u)

I : 인덱스 변화 횟수 (l = m + 1, r = m - 1)

J : m 변수에 값을 쓰는 횟수

 

C1, C2, I, J 모두 반복문을 도는 동안 모두 일어나므로 반복횟수 m` 에 대해서 아래와 같이 계산된다.

 

(C1 + C2 + I + J) * m`

 

한번 반복을 실행할 때 실행하는 기능이 선형 탐색 알고리즘보다 많다.

따라서 전체 코드 실행량을 기준으로 볼 때 이분탐색의 코드 실행량이 더 많아 한번 반복할 때 실행시간이 길다.

m` 값은 코드의 실행을 트리로 표현하면 거의 완전 이진트리 형태임을 확인하였으므로 값을 찾아도 못 찾아도 log(N) 정도의 반복 횟수를 갖는다.

 

그리고 C1, C2, I, J 모두 각 반복마다 한번씩 실행되므로, C1 == C2, I == J 라고 가정하면, C1 + C2 + I + J = 2(C1 + I) 로 나타낼 수 있다.

이는 위에서 작성한 sentinel 선형 탐색에서 한번 반복시 걸리는 시간의 2배임을 알 수 있다.

 

이분 탐색의 실행시간이 2(C1 + I) * m` 이고, 선형 탐색의 실행시간이 (C1 + I) * m 에 관련되어있으므로

이분 탐색이 더 빨라진다는 것은

 

2(C1 + I) * m` < (C1 + I) * m

2 * m` < m

m/m` > 2

 

의 조건을 만족하면 된다.

따라서 이분탐색이 위에서 작성한 효율적인 선형탐색보다 덜 시간이 걸리는 조건은 아래와 같이 계산할 수 있다.

선형 탐색의 반복 횟수 m 과 이분 탐색의 반복횟수 m` 을 비교하였을 때

 

m / m` =  { (N+1) / 2 } / log N > 2

 

이면 된다.

그리고 이 조건을 만족하는 N의 사이즈는 N이 15 이상일 때 만족한다.

 

바꿔말하면, N의 사이즈가 15보다 작을 때는 이분탐색보다 저 sentinel 선형 탐색을 사용하는 것이 실행 시간 측면에서 더 효율적임을 알 수 있다.