이진 검색(Binary Search)이란? - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 중 14찾기

이진 검색(Binary Search)이란?

이진 검색(Binary Search)은 정렬된 배열이나 리스트에서 특정 원소를 찾는 알고리즘 중 하나입니다. 이 알고리즘은 배열이나 리스트를 중간에서 나누고, 찾고자 하는 원소가 중간 값과 비교하여 어느 부분에 위치하는지를 판단하는 방식으로 동작합니다. 이렇게 하면 검색 대상이 현재 부분 배열의 왼쪽 또는 오른쪽에 위치할 것이므로, 검색 범위를 절반으로 줄일 수 있습니다.

이진 검색의 단계는 다음과 같습니다:

배열이나 리스트를 정렬합니다.
검색 대상을 현재 배열 또는 리스트의 중간 값과 비교합니다.
검색 대상이 중간 값보다 작으면 왼쪽 부분 배열 또는 리스트를 대상으로 이진 검색을 반복합니다.
검색 대상이 중간 값보다 크면 오른쪽 부분 배열 또는 리스트를 대상으로 이진 검색을 반복합니다.
검색 대상이 중간 값과 동일하면 해당 위치를 반환하고 검색을 종료합니다.
검색 범위가 더 이상 없으면 검색 실패로 처리합니다.
이진 검색은 평균적으로 시간 복잡도가 O(log n)이며, 정렬된 데이터에서 빠르게 동작하는 장점이 있습니다. 이 알고리즘은 반으로 나누는 특성 때문에 탐색 범위를 효율적으로 줄일 수 있기 때문에 성능이 우수합니다.

이진 검색 방법 코드 실례

첫 번째 비교 (mid = 7)

중간 지점은 (1 + 15) / 2 = 8입니다.
배열의 인덱스 7에 위치한 값은 8입니다.
14는 8보다 크기 때문에 검색 범위를 오른쪽으로 좁힙니다.

두 번째 비교 (mid = 11)

새로운 중간 지점은 (8 + 15) / 2 = 11입니다.
배열의 인덱스 11에 위치한 값은 12입니다.
14는 12보다 크기 때문에 검색 범위를 오른쪽으로 좁힙니다.

세 번째 비교 (mid = 13)

새로운 중간 지점은 (12 + 15) / 2 = 13입니다.
배열의 인덱스 13에 위치한 값은 14입니다.
찾고자 하는 값 14를 찾았습니다.
이렇게 3번의 비교를 통해 14를 찾을 수 있습니다. 

이진 검색 방법 코드 예시

이 예시에서 binarySearch 함수는 정수 배열에서 특정 값을 찾기 위한 이진 검색을 수행합니다. 배열은 정렬된 상태여야 합니다. 검색 대상이 배열에 있는 경우 해당 인덱스를 반환하고, 없는 경우 -1을 반환합니다. 이 예시에서는 원소 7을 찾는 것으로 설정되어 있습니다.

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // 중간 값이 타겟과 동일한지 확인
        if (arr[mid] == target)
            return mid;

        // 중간 값이 타겟보다 작으면 오른쪽 부분 탐색
        if (arr[mid] < target)
            low = mid + 1;
        // 중간 값이 타겟보다 크면 왼쪽 부분 탐색
        else
            high = mid - 1;
    }

    // 찾지 못한 경우 -1 반환
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, 0, n - 1, target);

    if (result != -1)
        printf("원소 %d은(는) 배열의 인덱스 %d에 있습니다.\n", target, result);
    else
        printf("원소 %d은(는) 배열에 존재하지 않습니다.\n", target);

    return 0;
}

 

코드에서 target으로 지정된 값이 배열에서 어떤 인덱스에 위치하는지 결과를 출력하는 부분을 살펴보겠습니다.

if (result != -1)
    printf("원소 %d은(는) 배열의 인덱스 %d에 있습니다.\n", target, result);
else
    printf("원소 %d은(는) 배열에 존재하지 않습니다.\n", target);

 

이 코드는 binarySearch 함수의 결과에 따라 메시지를 출력합니다. 만약 result가 -1이 아니라면, target이 배열에서 발견되었다는 것이므로 해당 인덱스를 출력합니다. 그렇지 않으면 target이 배열에 없다는 메시지를 출력합니다.

위 예시에서 target으로 설정된 값은 7이고, 배열은 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}입니다. 이 경우에는 배열의 인덱스 6에 해당하는 값이 7이기 때문에 결과는 다음과 같습니다

원소 7은(는) 배열의 인덱스 6에 있습니다.