이진탐색 (C#) 제네릭

public static int BinarySearch<T>(T[] arr, T target, Func<T, T, int> comparer)
    {
        if (arr == null || arr.Length == 0 || comparer == null)
        {
            return -1;
        }
 
        int left = 0;
        int right = arr.Length - 1;
 
        // 왼쪽 포인터가 오른쪽 포인터보다 작거나 같을 때까지 반복한다.
        while (left <= right)
        {
            int mid = left + (right - left) / 2; // 중간 인덱스를 계산한다.
 
            int comparison = comparer(arr[mid], target); // 중간 인덱스의 값과 탐색할 값을 비교한다.
            if (comparison == 0)
            {
                return mid; // 중간 인덱스의 값이 탐색할 값과 같으면 중간 인덱스를 반환한다.
            }
            else if (comparison < 0)
            {
                left = mid + 1; // 중간 인덱스의 값이 탐색할 값보다 작으면 왼쪽 포인터를 중간 인덱스 + 1로 이동시킨다.
            }
            else
            {
                right = mid - 1; // 중간 인덱스의 값이 탐색할 값보다 크면 오른쪽 포인터를 중간 인덱스 - 1로 이동시킨다.
            }
        }
 
        return -1; // 탐색할 값이 배열에 없으면 -1을 반환
    }

코딩테스트 사용처

• 순차적인 배열 탐색으로는 시간 초과가 나는 문제에서 사용한다.
• 시간 복잡도 : O(logN)로 그냥 순회하는 O(N)보다 빠르다.
• 이분 탐색 + 다익스트라 등 다른 유형과 연계되는 문제가 출제될 수 있다.

정렬된 배열에서 특정 값 찾기: 이진 탐색은 정렬된 배열에서 특정 값을 찾는 데 효과적이다. 중간값을 계속해서 확인하면서 원하는 값이 중간값보다 작으면 왼쪽 부분을, 크면 오른쪽 부분을 탐색하여 범위를 좁혀나가며 원하는 값을 찾아낸다.

 

최적화 문제에서 최솟값 또는 최댓값 찾기: 이진 탐색은 최적화 문제에서 최소 또는 최대 값을 찾는 데 효과적이다. 예를 들어, 공장에서 생산하는 부품의 길이를 조절해야 할 때, 부품의 길이에 따라 특정 조건이 만족되는 최소 또는 최대 길이를 찾아야 하는 경우 이진 탐색을 사용할 수 있다.

 

고정된 크기의 구간에서 조건을 만족하는 구간 찾기: 정렬된 데이터에서 고정된 크기의 구간 내에서 특정 조건을 만족하는 구간을 찾아야 하는 경우에도 이진 탐색을 사용할 수 있다. 예를 들어, 학생들의 성적이 정렬된 배열로 주어졌을 때, 특정 점수 범위 내에 있는 학생들의 수를 구하는 문제를 풀 수 있다.