Binary Search

[LeetCode] 2529. Maximum Count of Positive Integer and Negative Integer

20250312 Daily Question

정렬된 배열 nums가 오른차순으로 주어질 때, 양수의 개수와 음수의 개수 중 더 큰 값을 반환하라.

easy 다운 문제였다. 그냥 모든 요소를 돌면서 음수, 양수를 세고 Math.max로 더 큰 값을 반환하게 코드를 짰다. 당연히 통과를 했고 릿코드가 원하는(??) 알고리즘이 어떤건지 찾아보았다.

릿코드 솔루션 을 참고했다.

var maximumCount = function (nums) {
    let pos = 0;
    let neg = 0;

    nums.forEach((num) => {
        if (num > 0) pos++;
        else if (num < 0) neg++;
    })

    return Math.max(pos, neg)
};

내 코드는 모든 요소를 확인하는 완전탐색이었다. 솔루션을 보니 이진 탐색으로 접근하는 풀이였다. 물론 해당 문제의 조건이 크지 않아서 완전 탐색으로 풀어도 괜찮았지만!! 이진 탐색에 대해 알아보자.

Binary Search

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘이다. 보통 O(log N) 의 시간 복잡도를 가지며, 배열을 반씩 나누면서 검색 범위를 좁혀나가는 방식이다.

이진 탐색의 핵심 개념은 다음과 같다.

1. 배열이 정렬되어 있어야 한다.
이진 탐색은 정렬된 배열에서만 동작한다. 배열이 정렬되지 않았다면, 중간 값이 목표값보다 크거나 작은지를 판단할 수 없기 때문이다.

2. 검색 범위를 줄여나간다. (반씩 나누기)
배열의 가운데(mid) 값을 확인하고, 찾는 값이 mid보다 크면 오른쪽을 탐색.
찾는 값이 mid보다 작거나 같으면 왼쪽을 탐색.
이 과정을 반복하면서 검색 범위를 줄여나간다.

3. 시간 복잡도: O(log N)
배열을 반씩 나누면서 탐색하기 때문에 O(log N)의 시간 복잡도를 가진다. 즉, 데이터가 100만 개라도, 최대 20번 정도의 비교만으로 찾을 수 있다!

O(log N)

이진 탐색의 핵심은 매 단계마다 검색 범위를 반으로 줄이는 것이다.
즉, 배열의 크기가 N이라면, 한 번 검사할 때마다 N → N/2 → N/4 → ... 이렇게 줄어든다.

이 과정을 수식으로 표현하면 다음과 같다.

1단계 후: N/2
2단계 후: N/4
3단계 후: N/8
…
k단계 후: N / 2^k

이제 언제 탐색이 끝나는지 생각해 보자. 탐색이 끝나는 시점은 남은 요소가 1개 이하가 되는 순간이다.
즉, 다음 방정식을 만족하는 k를 찾으면 된다.

양변에 log₂()를 취하면

$k = \log_2 N$

즉, 이진 탐색의 시간 복잡도는 O(log N)이 된다!

refactor

var maximumCount = function(nums) {
    let negCount = binarySearch(nums, 0);
    let posCount = nums.length - binarySearch(nums, 1);
    
    return Math.max(negCount, posCount);
};

function binarySearch(nums, target) {
    let left = 0, right = nums.length;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}