정렬된 배열에서 특정 수의 개수 구하기 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 27, p 367

 

재귀함수로 구현한 이진 탐색 코드를 참고하여 풀이했습니다.
타겟 값이 있는 인덱스를 result라는 집합에 모두 추가하고 이 집합의 길이를 반환했습니다. 기존의 이진 탐색과 동일하지만, 중간값이 타겟과 같은 경우 현재 중간값을 result 집합에 추가해주었고, 왼쪽과 오른쪽 모두에 타겟이 더 있을 수 있으므로 end를 mid-1로 갱신한 탐색, start를 mid+1로 갱신한 탐색 모두를 진행하도록 했습니다. 타겟 원소가 하나도 없으면 -1을 출력하도록 했으므로 result의 길이가 0보다 크면 len(result)를, 그렇지 않으면 -1을 출력하도록 했습니다.

 

https://codlingual.tistory.com/189

이진 탐색

 

# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, target, start, end, result):
    if start > end:
        # x인 원소가 하나도 없다면 -1 출력 
        return len(result) if len(result) > 0 else -1 
    
    mid = (start + end) // 2 
    
    # 중간값이 타겟인 경우 
    if array[mid] == target:
        # 현재 인덱스를 result 집합에 추가 
        result.add(mid)
        # 현재 인덱스보다 작은 쪽, 큰 쪽 모두 가보기 
        binary_search(array, target, start, mid - 1, result)
        binary_search(array, target, mid + 1, end, result)
        
    # 중간값이 타겟보다 큰 경우 
    elif array[mid] > target:
        binary_search(array, target, start, mid - 1, result)
        
    # 중간값이 타겟보다 작은 경우 
    else:
        binary_search(array, target, mid + 1, end, result)
        
    # x인 원소가 하나도 없다면 -1 출력 
    return len(result) if len(result) > 0 else -1 

def solution(N, x, array):
    return binary_search(array, x, 0, N-1, result=set())