[Algorithm] 순차 탐색(Sequential search)과 이진 탐색(Binary search)

순차 탐색(Sequential search)

---

순차 탐색이란 나열된 데이터를 처음부터 끝까지 하나하나 순차적으로 탐색하면서 원하는 데이터를 찾는 방법을 말합니다.

코드 구현이 쉽고 알고리즘이 간단하다는 장점이있지만,

다른 탐색에 비해 상대적으로 시간이 많이 걸리는 단점이 있습니다.

최악의 경우, 순차 탐색은 1부터 n까지 모든 데이터를 탐색해야하기 떄문에 순차 탐색의 시간복잡도는 O(n)이 됩니다.

#include <stdio.h>

int main(){
    int ary[10] = {1, 3, 6, 2, 4, 5, 10, 8, 7, 9};
    int len = sizeof(ary)/sizeof(int);
    int target = 0;
    scanf("%d", &target);
    int index = FirstFind(ary, len, target);
    
    if(index == -1){
        printf("순차 탐색에 실패하셨습니다\n");
    }
    else{
        printf("값을 찾았습니다! --> ary[%d]에 값 %d가 있습니다\n", index, target);
    }
}

int FirstFind(int ary[], int len, int target)
{
    for(int i = 0; i<len; i++)
    {
        if(ary[i] == target){
            return i;
        }
    }
    return -1;
}

이진 탐색(Binary search)

---

이진 탐색이란 정렬된 데이터에서 탐색 범위를 반으로 나눠가면서, 원하는 데이터를 얻을 때까지 반복하는 알고리즘을 말합니다.

순차 탐색에 비해 걸리는 시간이 훨씬 적고 실행 속도가 빠르다는 장점이 있지만,

데이터가 반드시 오름차순으로 정렬되어있어야 한다는 단점이 있습니다.

 

이진 탐색에서 총 데이터의 개수를 16(2^4)개라고 해봅시다.

그러면 최악의 경우, 줄여나가는 탐색의 범위가 16, 8, 4, 2, 1이 됩니다.

즉 탐색의 범위가 1이 될 때, 해당 데이터가 우리가 찾는 데이터가 되고 알고리즘이 종료됩니다.

이 때 코드의 실행 횟수는, 탐색 범위를 반으로 줄이는 횟수(4) + 마지막 데이터를 선택(1) = 4 + 1이 됩니다.

 

만약 데이터의 개수를 n개라고 하면, 줄여나가는 탐색 범위는 n, n/2, n/4  ... n/2^k(=1)이 되고

이 때 코드의 실행 횟수는, 탐색 범위를 반으로 줄이는 횟수(k) + 마지막 데이터를 선택(1) = 2^k + 1이 됩니다

이 때 2^k = n 이므로 T(n) = k+1 = log2n + 1이 됩니다.

따라서 이진 탐색의 시간복잡도는 O(logn)이 됩니다.

#include <stdio.h>

int main(int argc, const char * argv[]) {
   
    int ary[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 0;
    scanf("%d", &target);
    int index = binearySearch(ary, sizeof(ary)/sizeof(int), target);
    
    if(index == -1){
        printf("이진 탐색에 실패하셨습니다\n");
    }
    
    else
        printf("ary[%d]에 값 %d가 있습니다\n", index, ary[index]);
    
    return 0;
}

int binearySearch(int ary[], int count, int target){
    int first = 0;
    int last = count;
    int mid;
   
    while(first<=last){
        mid = (first+last)/2;
        
        if(ary[mid] == target)
            return mid;
        else{
            if(target < ary[mid]){
                last = mid -1;
            }
            else
                first = mid +1;
        }
    }
    return -1;
}