[자료구조] 이진탐색 알고리즘

[알고리즘 소개] 

 

1) 이진탐색 알고리즘에서는 배열 인덱스의 시작과 끝을 각각 0과 마지막 값으로 둔다. 그리고 0과 마지막 값을 더한 값을 2로 나눈 결과값을 인덱스값으로 하여, 인덱스 값이 target값보다 큰지 작은지를 판단한다.

2) 1의 결과를 토대로 target값보다 크다면 오른쪽을, target값보다 작다면 왼쪽 절반을 취한다. 이를 반복한다.

3) 순차 탐색하는 것 보다 좋은 성능임을 확인한다.(순차 탐색보다 탐색량이 줄음)

 

[구현]

int Bsearch(int arr[],int len, int target)
{
    int first = 0;
    int last = len - 1;
    int mid;

    while(first <= last){
    mid = (first + last) / 2
    if(target == arr[mid])
{
    return mid;
}
    else{
    if(target <arr[mid])
        last = mid - 1
    else
        first = mid + 1
    }
    }
    return -1;
    }

 

[시간 복잡도 ]

이진 탐색 알고리즘의 시간 복잡도는 O(log₂n)이다. 여기서 n은 배열의 요소 수를 나타낸다. 로그의 밑(base)이 2인 로그(log₂)를 사용하는 이유는 각 단계에서 검색 범위가 2로 나누어지기 때문이다.(탐색시마다 절반으로 줄음) 따라서 이진 탐색의 시간 복잡도는 정확하게 O(log₂n)이다. 이로써 각 단계에서 검색 범위를 반으로 줄이는 특성이 더 명확하게 나타난다.