[자료구조] 이원 탐색, 순환 이원 탐색

이원 탐색

이미 정렬된 배열 a[0] ... a[n-1]에서 x=a[j]인 j를 반환

- left, right: 탐색하고자 하는 리스트의 왼쪽, 오른쪽 끝

- 초기값 left = 0, right = n-1

- 리스트의 중간 위치 middle = (left/right)/2

- a[middle]과 x 비교

 

1) x < a[middle]

-> right = middle-1

2) x = a[middle]

-> middle 반환

3) x > a[middle]

-> left = middle+1

 

int BinarySearch(int *a, const int x, const int n)
{ // 정렬된 배열 a[left], ..., a[right]에서 x 탐색
    int left = 0, right = n - 1;
    while (left <= right)
    {
        int middle = (left + right) / 2;
        if (x < a[middle])
            right = middle - 1;
        else if (x > a[middle])
            left = middle + 1;
        else
            return middle;
    }          // if의 끝
    return -1; // 발견되지 않음
}

 

시간복잡도 - O(log₂N)

 

순환 알고리즘

수행이 완료되기 전에 자기 자신을 다시 호출 

- 직접 순환: 함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출

- 간접 순환: 호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출

 

순환 이원 탐색

int BinarySearch(int *a, const int x, const int left, const int right)
{ // 정렬된 배열 a[left], ..., a[right]에서 x 탐색
    if (left <= right)
    {
        int middle = (left + right) / 2;
        if (x < a[middle])
            return BinarySearch(a, x, left, middle - 1);
        else if (x > a[middle])
            return BinarySearch(a, x, middle + 1, right);
        return middle;
    }          // if의 끝
    return -1; // 발견되지 않음
}

 

시간복잡도 - O(log₂N)