C++로 이진 탐색으로 찾을 수 있는 요소 개수 구하기

문제 이해하기

중복되지 않는 정수들로 이루어진 배열 nums가 있다고 가정해 봅시다. 우리가 구해야 할 것은, 표준 이진 탐색(binary search)을 수행했을 때 여전히 성공적으로 찾을 수 있는 정수의 개수입니다.

일반적으로 이진 탐색은 정렬된 배열에서만 동작하지만, 배열이 정렬되어 있지 않더라도 탐색 과정에서 우연히 목표 값이 가운데 위치에 걸리면 값을 발견할 수 있습니다. 이 문제는 바로 그런 '운 좋게 찾을 수 있는' 원소가 몇 개인지 세는 것입니다.

예를 들어 입력이 [2, 6, 4, 3, 10]이라면 출력은 3이 됩니다. 값 4는 첫 번째 비교에서 바로 찾을 수 있고, 2는 두 번째 반복에서, 10은 세 번째 반복에서 찾을 수 있습니다. 반면 6과 3은 어떤 경로로 탐색해도 발견되지 않습니다.

접근 방법

해결 방법은 단순합니다. 배열의 모든 원소에 대해 실제로 표준 이진 탐색을 수행해 보고, 탐색에 성공하는 경우의 수를 세면 됩니다. 알고리즘은 다음과 같습니다.

목표 값 target과 배열 nums를 받는 help() 함수를 정의합니다.
low := 0, high := nums의 크기 - 1로 초기화합니다.
low <= high인 동안 다음을 반복합니다.
- mid := low + (high - low) / 2
- nums[mid]가 target과 같으면 true를 반환합니다.
- nums[mid] < target이면 low := mid + 1로 갱신합니다.
- 그렇지 않으면 high := mid - 1로 갱신합니다.
반복이 끝나면 false를 반환합니다.
메인 함수에서는 ret := 0으로 초기화한 뒤, 배열의 각 원소 i에 대해 help(i, nums)의 결과를 더하고 최종적으로 ret을 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해해 봅시다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool help(int target, vector<int> & nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target)
            return true;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
    int solve(vector<int> & nums) {
        int ret = 0;
        for (int i : nums) {
            ret += help(i, nums);
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<int> v = {2,6,4,3,10};
    cout << (ob.solve(v));
}

입력

{2,6,4,3,10}

출력

복잡도 분석

배열의 각 원소마다 한 번의 이진 탐색을 수행하며, 이진 탐색 한 번은 O(log n)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(n log n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.