1.5.3 이진 검색

문제 1-3 정렬된 배열에서 특정 값을 찾는 함수를 작성하세요.

해결책 정렬된 배열에서 값을 검색할 때는 이진 검색을 사용합니다. 각 단계에서 중간 위치를 찾습니다. 찾는 값은 중간값보다 크거나 작습니다. 배열의 왼쪽 또는 오른쪽을 검색합니다. 각 단계에서 검색 공간의 절반을 제거하므로 선형 검색보다 효율적인 알고리즘입니다.

1. 오름차순 또는 내림차순으로 정렬된 데이터는 이진 검색을 사용해 효율적으로 검색할 수 있습니다. 각 단계에서 검색 공간을 절반으로 줄입니다.

2. 각 단계에서 찾는 값과 중간값을 비교합니다. 중간값이 찾는 값이라면 중간값의 인덱스를 반환합니다.

3. 찾는 값이 중간값보다 작으면 배열의 왼쪽 절반을 검색합니다.

4. 찾는 값이 중간값보다 크면 배열의 오른쪽 절반을 검색합니다.

5. 찾는 값을 발견하면 그 값의 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

해결책 1-3

int BinarySearch(int arr[], int size, int value)
{
    int low = 0, mid;
    int high = size - 1;
    while (low <= high) {
        mid = low + (high - low) / 2; /* 오버플로 방지 */
        if (arr[mid] == value) {
            return mid;
        }
        else if (arr[mid] < value) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

분석 시간 복잡도는 O(logn)입니다.