C# 이진 검색(Binary Search) 개념부터 구현까지 완벽 정리

C# 이진 검색이란?

이진 검색(Binary Search)은 정렬된 배열에서만 동작하는 대표적인 탐색 알고리즘입니다. 찾으려는 값을 배열의 중간 요소와 비교하고, 값이 일치하지 않으면 해당 값이 존재할 수 없는 절반을 제거한 뒤 나머지 절반에서 다시 탐색을 반복합니다. 탐색 범위가 매번 절반씩 줄어들기 때문에 선형 검색보다 훨씬 빠른 속도로 원하는 값을 찾을 수 있다는 것이 가장 큰 장점입니다.

동작 원리

예를 들어 배열에서 62라는 값을 찾는다고 가정해 보겠습니다. 먼저 배열의 중간 요소(mid)를 확인합니다. 중간 값이 62보다 크다면 왼쪽 부분은 제거되고, 오른쪽 부분만 남겨 두고 탐색을 계속 진행합니다.

이진 검색의 시간 복잡도

이진 검색의 성능은 아래 표와 같이 정리할 수 있습니다.

C# 이진 검색 구현 예제

다음은 C#으로 이진 검색을 구현한 메서드입니다. 최솟값 인덱스(minNum)와 최댓값 인덱스(maxNum)를 기준으로 중간 위치를 계산하며, 키 값과 비교해 탐색 범위를 절반씩 좁혀 나갑니다.

public static object BinarySearchDisplay(int[] arr, int key) {
    int minNum = 0;
    int maxNum = arr.Length - 1;

    while (minNum <= maxNum) {
        int mid = (minNum + maxNum) / 2;
        if (key == arr[mid]) {
            return ++mid;
        } else if (key < arr[mid]) {
            maxNum = mid - 1;
        } else {
            minNum = mid + 1;
        }
    }
    return "None";
}

위 코드에서 주목할 점은 다음과 같습니다.
- 키 값이 중간 요소와 일치하면 해당 위치(1부터 시작하는 인덱스)를 반환합니다.
- 키 값이 중간 요소보다 작으면 탐색 범위를 왼쪽 절반으로 축소합니다.
- 키 값이 중간 요소보다 크면 탐색 범위를 오른쪽 절반으로 축소합니다.
- 모든 범위를 탐색한 후에도 값을 찾지 못하면 "None"을 반환합니다.

이처럼 이진 검색은 정렬된 데이터에서 O(log n)의 뛰어난 성능을 보장하기 때문에, 대용량 데이터를 다루는 검색 기능에 널리 활용됩니다.