[이코테] 이진 탐색_정렬된 배열에서 특정 수의 개수 구하기 (python)

나의 풀이

1.

n, x = map(int, input().split())
num = list(map(int, input().split()))
#이진 탐색(재귀 함수) 만들기
#1. x값이 시작되는 인덱스 찾기
def search_start(arr, target, start, end):
    if start > end:
        return -1
        
    mid = (start + end) // 2 #중간점
	#index가 0 이거나 x값이 이전 수보다 크고, 중간점이 x랑 같을 때
	#즉, x값이 시작하는 인덱스일 때
    if (mid == 0 or arr[mid - 1] < target) and arr[mid] == target:
        return mid #인덱스 반환
        
	#중간점을 좁혀가며
    elif arr[mid] >= target:
        return search_start(arr, target, start, mid - 1)
        
    else:
        return search_start(arr, target, mid + 1, end)
#1. x값이 끝나는 인덱스 찾기          
def search_end(arr, target, start, end):
    if start > end:
        return -1
        
    mid = (start + end) // 2 #중간점
	#index가 끝이거나 x값이 다음 수보다 작고, 중간점이 x랑 같을 때
	#즉, x값이 끝나는 인덱스일 때
    if (mid == n - 1 or arr[mid + 1] > target) and arr[mid] == target:
        return mid #인덱스 반환
    
	#중간점을 좁혀가며    
    elif arr[mid] >= target:
        return search_end(arr, target, start, mid - 1)
        
    else:
        return search_end(arr, target, mid + 1, end)        
        
start_v = search_start(num, x, 0, n - 1)
end_v = search_end(num, x, 0, n - 1)

#x값이 수열에 없을때, -1 출력
if start_v == end_v == -1:
    print(-1)
else: #끝 인덱스 - 시작 인덱스 + 1
    print(start_v - end_v + 1)

• 포인트는 두개~

1. 시작 인덱스와 끝 인덱스를 찾아서 빼주기
2. 시작과 끝 함수에서 각각 어떻게 아래/위로 범위를 좁혀나갈지
   : if (mid == 0 or arr[mid - 1] < target) and arr[mid] == target과 if (mid == n - 1 or arr[mid + 1] > target) and arr[mid] == target