[Algorithm] C - 이진 탐색(Linear Search)

요약

시간 복잡도 : O(log N)

• 데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가는 검색하는 검색 알고리즘
• 오름차순 또는 내림차순으로 정렬된 데이터 구조에서만 사용할 수 있음
• 검색이 반복될 때마다 검색 범위가 반으로 좁혀지므로 검색 속도가 빠름
• 검색 범위를 맨 앞, 맨 끝, 중앙 요소로 두고 중앙 요소의 값으로 학인함

이진 탐색(Binary Search)

이진 탐색이란 데이터가 오름차순 또는 내림차순으로 정렬되어 있을 때 검색하는 정렬 알고리즘이다.
이진 탐색은 정렬되지 않은 데이터에서는 사용할 수 없으나, 선형 검색보다 빠르게 검색할 수 있는 장점이 있다.
데이터의 중간 값을 확인해 검색 범위를 반씩 좁혀가며 검색하는 구조를 가지고 있다.

먼저 정렬된 배열이 있다고 가정한다.

[5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95]

39를 찾는다는 과정으로 보면, 배열에서 중간 요소부터 먼저 검색하기 시작한다.

중간 요소의 값은 31([5])이며, 이 값은 검색하고자 하는 값(39)보다 낮은 값이다.
그러므로 중간 요소보다 뒤에 있다고 생각할 수 있다.(배열은 오름차순)

찾고자 하는 값이 중간 요소보다 뒤에 있으니, 검색 범위를 [6]부터 [10]까지 좁히고, 여기서 중간 요소인 [8]을 검색한다.
[8]의 값을 확인하니 68로, 39보다 높은 값이므로 [8]의 앞쪽 범위로 다시 검색 범위를 좁힌다.

다시 검색 범위가 [6]과 [7]로 좁혀졌고 이제 검삭 대상은 2개가 되었다.
이때 두 요소 중 아무거나 선택해도 상관 없지만 앞 쪽 요소를 먼저 확인한다.
(6과 7의 중간 값은 (6 + 7) / 2로, 나머지를 버려 6이 되기 때문에 앞 요소를 먼저 확인)

[6]의 값을 확인해 보니 39로, 원하는 값과 일치하므로 검색에 성공했다.

검색 과정

이러한 n개의 요소가 오름차순으로 늘어진 배열에서 키를 이진 탐색으로 검색하기 위해 앞, 중간, 끝 인덱스를 나눈다.

• pl : 맨 앞 인덱스
• pr : 맨 끝 인덱스
• pc : 중앙 인덱스

검색을 시작할 때 pl은 0으로, pr은 n - 1, pc는 (n - 1) / 2로 초기화 한다.

이진 탐색을 하다가 원하는 값을 찾지 못할 경우, 2가지의 방법으로 범위를 좁혀나갈 수 있다.

1. pc(중앙 인덱스) < Key 일 경우

pl ~ pc는 key보다 작은 값이 확실해졌으므로, pc + 1 ~ pr로 검색 범위를 좁힐 수 있다.
그 다음 pl의 값을 중앙 인덱스 + 1인 pc + 1로 업데이트 한다. (검색 범위가 반으로 좁혀짐)

2. pc(중앙 인덱스) < Key 일 경우

pc ~ pr은 key보다 큰 값이 확실해 졌으므로, pl ~ pc - 1로 검색 범위를 좁힐 수 있다.
그 다음 pr의 값을 중앙 인덱스 -1인 pc - 1로 업데이트 한다. (검색 범위가 반으로 좁혀짐)

이러한 경우로 볼 때 이진 탐색의 종료 조건은 2가지로 좁힐 수 있다.

• pc와 key의 값이 일치하는 경우
• 검색 범위가 더 이상 없는 경우

이진 탐색의 실패

아래 그림은 배열에서 6을 검색하는 과정으로, 이진 탐색의 실패 과정을 나타낸다.

1. 중앙 요소의 값이 31이므로 키 값이 6보다 크므로 검색 범위를 [0] ~ [4]로 좁힌다.
2. 새로 검색할 범위의 중앙 값이 15([2])이므로 키 값보다 크다. 범위를 [0] ~ [1]로 좁힌다.
3. 좁힌 범위의 중앙 값인 5([0])은 6보다 크므로 pl을 pc + 1로 업데이트한다. 그러면 pl과 pr은 1이 된다.
4. 마지막 남은 값이 7이므로 키 값인 6보다 크다. pr을 pc - 1(0)으로 업데이트 하면, pl이 pr보다 커지므로 검색 범위를 벗어난다.
5. 검색 범위를 벗어났고, 키를 찾지 못하였으므로 검색에 실패한다.

예제 코드

#include <stdio.h>
#include <stdlib.h>

int BinarySearch(const int *a, int n, int key);

int main() {
    int i, n, key, index;
    int *x;
    
    printf("요소 개수 : ");
    scanf("%d", &n);
    
    x = malloc(sizeof(int) * n);
    
    printf("오름차순 입력\n");
    printf("x[0] : ");
    scanf("%d", &x[0]);
    
    for(i = 1; i < n; i++) {
        do {
            printf("x[%d] : ", i);
            scanf("%d", &x[i]);
            // 바로 앞의 값보다 작을 경우 다시 입력
        } while(x[i] < x[i - 1]);
    }
    
    printf("검색 값 : ");
    scanf("%d", &key);
    
    index = BinarySearch(x, n, key);
    
    if(index == -1) {
        printf("검색 실패!");
    }
    else {
        printf("%d 값은 x[%d]에 있음!\n", key, index);
    }
    
    free(x);

    return 0;
}

// a : 검색할 배열, n : 배열 사이즈, key : 찾을 값
int BinarySearch(const int *a, int n, int key)
{
    // 맨 앞 인덱스
    int pl = 0;
    
    // 맨 마지막 인덱스
    int pr = n - 1;
    
    // 중앙 인덱스
    int pc;
    
    do {
        // 중간 값
        pc = (pl + pr) / 2;
        
        // 검색 성공
        if(a[pc] == key) {
            return pc;
        }
        // 중앙 값이 key보다 작을 때
        else if(a[pc] < key){
            // pl의 값을 좁혀진 범위에서의 앞 인덱스로 업데이트
            pl = pc + 1;
        }
        // 중앙 값이 key보다 클 때
        else {
            // pr의 값을 좁혀진 범위에서의 끝 인덱스로 업데이트
            pr = pc - 1;
        }
    } while(pl <= pr);
    
    // 검색 실패
    return -1;
}

실행 결과

요소 개수 : 7
오름차순 입력
x[0] : 2
x[1] : 15
x[2] : 22
x[3] : 32
x[4] : 11
x[4] : 11
x[4] : 14
x[4] : 35
x[5] : 64
x[6] : 72
검색 값 : 15
15 값은 x[1]에 있음!

https://github.com/JeHeeYu/Algorithm/tree/main/Search/Binary%20Search

GitHub - JeHeeYu/Algorithm: 알고리즘 개념 및 문제 풀이

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편